Bubble Sort Program
Bubble Sort is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. It's not an efficient algorithm for large lists, but it's easy to understand and implement.
Problem Statement
Given an array of integers, we need to sort it using the Bubble Sort algorithm in ascending order.
Example
Let's take an example array: [9, 2, 1, 6, -3, 7, -2, 1, -5, 12]
Pass 1:
- Compare 9 and 2: Swap them → [2, 9, 1, 6, -3, 7, -2, 1, -5, 12]
- Compare 9 and 1: Swap them → [2, 1, 9, 6, -3, 7, -2, 1, -5, 12]
- Compare 9 and 6: Swap them → [2, 1, 6, 9, -3, 7, -2, 1, -5, 12]
- Compare 9 and -3: Swap them → [2, 1, 6, -3, 9, 7, -2, 1, -5, 12]
- Compare 9 and 7: Swap them → [2, 1, 6, -3, 7, 9, -2, 1, -5, 12]
- Compare 9 and -2: Swap them → [2, 1, 6, -3, 7, -2, 9, 1, -5, 12]
- Compare 9 and 1: Swap them → [2, 1, 6, -3, 7, -2, 1, 9, -5, 12]
- Compare 9 and -5: Swap them → [2, 1, 6, -3, 7, -2, 1, -5, 9, 12]
- Compare 9 and 12: No swap → [2, 1, 6, -3, 7, -2, 1, -5, 9, 12]
Pass 2:
- Compare 2 and 1: Swap them → [1, 2, 6, -3, 7, -2, 1, -5, 9, 12]
- Compare 6 and -3: Swap them → [1, 2, -3, 6, 7, -2, 1, -5, 9, 12]
- Compare 6 and 7: No swap → [1, 2, -3, 6, 7, -2, 1, -5, 9, 12]
- Compare 7 and -2: Swap them → [1, 2, -3, 6, -2, 7, 1, -5, 9, 12]
- Compare 7 and 1: Swap them → [1, 2, -3, 6, -2, 1, 7, -5, 9, 12]
- Compare 7 and -5: Swap them → [1, 2, -3, 6, -2, 1, -5, 7, 9, 12]
- Compare 7 and 9: No swap → [1, 2, -3, 6, -2, 1, -5, 7, 9, 12]
- Compare 9 and 12: No swap → [1, 2, -3, 6, -2, 1, -5, 7, 9, 12]
Pass 3:
- Compare 1 and 2: No swap → [1, 2, -3, 6, -2, 1, -5, 7, 9, 12]
- Compare 2 and -3: Swap them → [1, -3, 2, 6, -2, 1, -5, 7, 9, 12]
- Compare 2 and 6: No swap → [1, -3, 2, 6, -2, 1, -5, 7, 9, 12]
- Compare 6 and -2: Swap them → [1, -3, 2, -2, 6, 1, -5, 7, 9, 12]
- Compare 6 and 1: Swap them → [1, -3, 2, -2, 1, 6, -5, 7, 9, 12]
- Compare 6 and -5: Swap them → [1, -3, 2, -2, 1, -5, 6, 7, 9, 12]
- Compare 6 and 7: No swap → [1, -3, 2, -2, 1, -5, 6, 7, 9, 12]
- Compare 7 and 9: No swap → [1, -3, 2, -2, 1, -5, 6, 7, 9, 12]
Passes 4 through 9: No more swaps are needed as the array is already sorted.
The final sorted array is: [1, -3, -2, -5, 1, 2, 6, 7, 9, 12]
Idea to Solve
Bubble Sort works by repeatedly iterating through the array, comparing adjacent elements, and swapping them if they are in the wrong order. This process is repeated until the entire array is sorted.
Pseudocode
procedure bubbleSort(A : list of sortable items)
n = length(A)
repeat
swapped = false
for i = 1 to n-1
if A[i-1] > A[i]
swap A[i-1] and A[i]
swapped = true
end if
end for
until not swapped
end procedure
Algorithm Explanation
- Start by initializing a flag
swapped
tofalse
. - Iterate through the array using a loop from index 1 to n-1.
- If the element at index
i-1
is greater than the element at indexi
, swap them and setswapped
totrue
. - After the inner loop completes, if
swapped
is stillfalse
, it means no swaps were performed, and the array is already sorted. In this case, exit the loop. - Repeat steps 2-4 until no swaps are performed in a full pass through the array.
Code Solution
-
1) Bubble sort in java
2) Bubble sort in c++
3) Bubble sort in c
4) Bubble sort in c#
5) Bubble sort in vb.net
6) Bubble sort in php
7) Bubble sort in node js
8) Bubble sort in typescript
9) Bubble sort in python
10) Bubble sort in ruby
11) Bubble sort in scala
12) Bubble sort in swift
13) Bubble sort in kotlin
14) Bubble sort in golang
Time Complexity
The worst-case time complexity of Bubble Sort is O(n^2), where n is the number of elements in the array. This is because, in the worst case, you might need to perform n-1 comparisons in the first pass, n-2 in the second, and so on, resulting in (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 comparisons. The best-case time complexity is O(n) when the array is already sorted.
This article provides a simple explanation of the Bubble Sort algorithm, its working principle, and a step-by-step example. It also includes the Pseudocode and a brief analysis of its time complexity. Bubble Sort, although not very efficient for large arrays, is easy to understand and implement, making it a good introductory sorting algorithm.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment