Bubble sort is the simplest sorting technique among all the sorting techniques known to us. It is a simple sorting technique as it is very easy to understand, easy to implement, and also very easy to analyze. It is a comparison based sorting technique. The complexity of this sorting technique is very high and the complexity totally depends on the number of elements. In this sorting technique the pairs of the elements are compared from the beginning of the array and continue up to the last element for the first pass and after the first pass, the largest or the smallest element reaches the last according to the ascending or descending order of sorting respectively. In the second pass again the pairs of elements will be compared but it will continue up to the second last element of the array and so on.
PROCEDURE OF BUBBLE SORT WITH EXAMPLE:
Suppose there are 5 unsorted elements in array as following:
Now if the elements are sorted using the bubble sort technique, the number of passes required will be (5 - 1) = 4 i.e. if the number of elements of the array is n then n - 1 passes are required to sort the elements using the bubble sort technique.
For sorting the above-mentioned array in ascending order the following passes have to be followed:
The pairs of the elements will be compared and the largest element will be reached to the last of the array and the steps will be:
First, the first pair of elements will be compared and as 98 is greater than 12 it will be swapped.
The array will be:
Now the next pair will be compared and again it will be swapped as 98 is also greater than 45. The array now will be:
Similarly, 98 and 34 will be compared and will be swapped and the array will be:
Now for the first pass, the last pair of elements will be compared. In this case, 98 is greater than 21.
So, it will be swapped and at the end of the first pass the biggest element of the array i.e. 98 will be positioned at the last i.e. it's the final sorted position. After pass 1 the array will be:
In this pass, the total number of comparisons is: 5 - 1 = 4
The last element of the array has already reached its sorted position so in the 2nd pass the last element will not be taken in the pair of elements again.
At the beginning the array elements are:
The first pair of elements will be compared again and will not be swapped as 12 is lesser than 45. So the array will remain the same.
The next pair of elements is 45 and 34, after comparing these two elements will be swapped and the array will be:
For the 2nd pass, the last pair is 45 and 21 which will be swapped as 45 is greater than 21. The final array after 2nd pass:
After this pass, the last two elements 45 and 98 reached their sorted position. In this pass, the number of comparisons is 5 - 2 = 3
At the beginning of the 3rd pass the array elements are:
Here 45 and 98 are already positioned in their sorted position. Again the first pair of elements will be compared. There will be no swapping as 12 is lesser than 34. So the array elements will remain the same.
The second pair of this pass is 34 and 21, after comparison, the elements will be swapped as 34 is greater than 21. So the array after this pass is:
After this pass logically the last three elements should be sorted already. Only one pair i.e. the first pair would remain unsorted. But in this case, it can be seen that after this pass all the elements of the array are already sorted.
The total number of comparisons in this pass is 5 - 3 = 2
Though the elements are sorted already after this pass according to the logic of bubble sort the fourth pass will also be there.
At the starting of this pass the array is:
Here only the first pair will be compared and as 12 is already lesser than 21 it will not be swapped and the array will remain the same.
This is the final pass and the total number of comparisons of this pass is: 5 - 4 = 1
After this pass the final sorted array will be:
INPUT: An unsorted array a[6,2,4,1,…………….,n] OUTPUT: An sorted array a[1,2,3,4,5,…………..,n] (in ascending order) PROCESS: Step 1: [Taking the number of elements from the user] Read n Step 2: [Take the unsorted elements from the user in an array] For i=0 to n Read arr[i] Step 3: [Print the unsorted array] For i=0 to n Print arr[i] Step 4:[Sorting the unsorted elements] For i=0 to i<n repeat For j=0 to j<n-i-1 If(a[j]>a[j+1]) then Set t <- a[j] Set a[j] <- a[j+1] Set a[j+1] <- t [End of ‘If’] [End of inner ‘For’ loop] [End of outer ‘For’ loop] Step 5: [Printing the sorted array] For i=0 to n Print arr[i] Step 6: Stop.
1. It is a comparison-based sorting technique.
2. It is an in-place sorting algorithm as it does not require any extra space for sorting.
3. The best-case complexity of the bubble sort algorithm is O(n)
4. The sorting is done by swapping the adjacent elements if they are not incorrect order
5. It is a stable sorting algorithm
1. Bubble sort is used in a polygon filling algorithm in graphics to sort the x coordinates of a particular scan line.
2. The concept of sorting can be understood by the learners easily by learning the bubble sort algorithm.
1. The algorithm is very easy to understand, implement, and analyze.
2. The coding of this algorithm is not lengthy, hence it is very simple.
3. It does not require extra spaces for sorting.
4. It performs well on a sorted array.
For this above algorithm the best case, average case, and the worst-case time complexity of bubble sort will be the same.
For n number of elements, the number of comparisons in the first pass is n - 1, in the second pass n - 2, and so on, and in the last pass the number of comparisons is 1 as explained earlier through example.
Therefore for n number of elements, the total number of comparisons to sort the array is:
If the algorithm can be changed such that if there is no swapping in a pass then the algorithm will stop working and will come out from the outer for loop. In that case, the best case (when the array is already sorted) there will be no swapping in the first pass and so the outer for loop will run only for ones.
The space complexity of this algorithm is O(1) as it is an in-place algorithm and it does not require any extra space for performing the sorting.