Bubble Sort-
- Bubble sort is the easiest sorting algorithm to implement.
- It is inspired by observing the behavior of air bubbles over foam.
- It is an in-place sorting algorithm.
- It uses no auxiliary data structures (extra space) while sorting.
How Bubble Sort Works?
- Bubble sort uses multiple passes (scans) through an array.
- In each pass, bubble sort compares the adjacent elements of the array.
- It then swaps the two elements if they are in the wrong order.
- In each pass, bubble sort places the next largest element to its proper position.
- In short, it bubbles down the largest element to its correct position.
Bubble Sort Algorithm-
The bubble sort algorithm is given below-
for(int pass=1 ; pass<=n-1 ; ++pass) // Making passes through array { for(int i=0 ; i<=n-2 ; ++i) { if(A[i] > A[i+1]) // If adjacent elements are in wrong order swap(i,i+1,A); // Swap them } } //swap function : Exchange elements from array A at position x,y void swap(int x, int y, int[] A) { int temp = A[x]; A[x] = A[y]; A[y] = temp; return ; } // pass : Variable to count the number of passes that are done till now // n : Size of the array // i : Variable to traverse the array A // swap() : Function to swap two numbers from the array // x,y : Indices of the array that needs to be swapped
Bubble Sort Example-
Consider the following array A-
Now, we shall implement the above bubble sort algorithm on this array.
Step-01:
- We have pass=1 and i=0.
- We perform the comparison A[0] > A[1] and swaps if the 0^{th} element is greater than the 1^{th} element.
- Since 6 > 2, so we swap the two elements.
Step-02:
- We have pass=1 and i=1.
- We perform the comparison A[1] > A[2] and swaps if the 1^{th} element is greater than the 2^{th} element.
- Since 6 < 11, so no swapping is required.
Step-03:
- We have pass=1 and i=2.
- We perform the comparison A[2] > A[3] and swaps if the 2^{nd} element is greater than the 3^{rd} element.
- Since 11 > 7, so we swap the two elements.
Step-04:
- We have pass=1 and i=3.
- We perform the comparison A[3] > A[4] and swaps if the 3^{rd} element is greater than the 4^{th} element.
- Since 11 > 5, so we swap the two elements.
Finally after the first pass, we see that the largest element 11 reaches its correct position.
Step-05:
- Similarly after pass=2, element 7 reaches its correct position.
- The modified array after pass=2 is shown below-
Step-06:
- Similarly after pass=3, element 6 reaches its correct position.
- The modified array after pass=3 is shown below-
Step-07:
- No further improvement is done in pass=4.
- This is because at this point, elements 2 and 5 are already present at their correct positions.
- The loop terminates after pass=4.
- Finally, the array after pass=4 is shown below-
Optimization Of Bubble Sort Algorithm-
- If the array gets sorted after a few passes like one or two, then ideally the algorithm should terminate.
- But still the above algorithm executes the remaining passes which costs extra comparisons.
Optimized Bubble Sort Algorithm-
The optimized bubble sort algorithm is shown below-
for (int pass=1 ; pass<=n-1 ; ++pass) { flag=0 // flag denotes are there any swaps done in pass for (int i=0 ; i<=n-2 ; ++i) { if(A[i] > A[i+1]) { swap(i,i+1,A); flag=1 // After swap, set flag to 1 } } if(flag == 0) break; // No swaps indicates we can terminate loop } void swap(int x, int y, int[] A) { int temp = A[x]; A[x] = A[y]; A[y] = temp; return; }
Explanation-
- To avoid extra comparisons, we maintain a flag variable.
- The flag variable helps to break the outer loop of passes after obtaining the sorted array.
- The initial value of the flag variable is set to 0.
- The zero value of flag variable denotes that we have not encountered any swaps.
- Once we need to swap adjacent values for correcting their wrong order, the value of flag variable is set to 1.
- If we encounter a pass where flag == 0, then it is safe to break the outer loop and declare the array is sorted.
Time Complexity Analysis-
- Bubble sort uses two loops- inner loop and outer loop.
- The inner loop deterministically performs O(n) comparisons.
Worst Case-
- In worst case, the outer loop runs O(n) times.
- Hence, the worst case time complexity of bubble sort is O(n x n) = O(n^{2}).
Best Case-
- In best case, the array is already sorted but still to check, bubble sort performs O(n) comparisons.
- Hence, the best case time complexity of bubble sort is O(n).
Average Case-
- In average case, bubble sort may require (n/2) passes and O(n) comparisons for each pass.
- Hence, the average case time complexity of bubble sort is O(n/2 x n) = Θ(n^{2}).
The following table summarizes the time complexities of bubble sort in each case-
Time Complexity | |
Best Case | O(n) |
Average Case | Θ(n^{2}) |
Worst Case | O(n^{2}) |
From here, it is clear that bubble sort is not at all efficient in terms of time complexity of its algorithm.
Space Complexity Analysis-
- Bubble sort uses only a constant amount of extra space for variables like flag, i, n.
- Hence, the space complexity of bubble sort is O(1).
- It is an in-place sorting algorithm i.e. it modifies elements of the original array to sort the given array.
Properties-
Some of the important properties of bubble sort algorithm are-
- Bubble sort is a stable sorting algorithm.
- Bubble sort is an in-place sorting algorithm.
- The worst case time complexity of bubble sort algorithm is O(n^{2}).
- The space complexity of bubble sort algorithm is O(1).
- Number of swaps in bubble sort = Number of inversion pairs present in the given array.
- Bubble sort is beneficial when array elements are less and the array is nearly sorted.
PRACTICE PROBLEMS BASED ON MERGE SORT ALGORITHM-
Problem-01:
The number of swapping needed to sort the numbers 8, 22, 7, 9, 31, 5, 13 in ascending order using bubble sort is- (ISRO CS 2017)
- 11
- 12
- 13
- 10
Solution-
In bubble sort, Number of swaps required = Number of inversion pairs.
Here, there are 10 inversion pairs present which are-
- (8,7)
- (22,7)
- (22,9)
- (8,5)
- (22,5)
- (7,5)
- (9,5)
- (31,5)
- (22,13)
- (31,13)
Thus, Option (D) is correct.
Problem-02:
When will bubble sort take worst-case time complexity?
- The array is sorted in ascending order.
- The array is sorted in descending order.
- Only the first half of the array is sorted.
- Only the second half of the array is sorted.
Solution-
- In bubble sort, Number of swaps required = Number of inversion pairs.
- When an array is sorted in descending order, the number of inversion pairs = n(n-1)/2 which is maximum for any permutation of array.
Thus, Option (B) is correct.
To gain better understanding about Bubble Sort Algorithm,
Next Article- Insertion Sort
Other Popular Sorting Algorithms-
Get more notes and other study material of Design and Analysis of Algorithms.
Watch video lectures by visiting our YouTube channel LearnVidFun.