Bubble sort is a very simple sorting algorithm of data structure. This is a comparison-based algorithm in which each pair of adjacent elements is compared and the elements are swapped if they are not in order.
Working of Bubble Sort
Suppose we have array A having 5 elements
| 32 | 51 | 27 | 85 | 66 |
pass 1:
(a) Compare first two element A1 and A2; 32 < 51, list will not altered.
| 32 | 51 | 27 | 85 | 66 |
(b) Compare A2 and A3; 51>27 , interchange 51 and 27
| 32 | 27 | 51 | 85 | 66 |
(c) Compare A3 and A4; 51 < 85 , list will not altered
| 32 | 27 | 51 | 85 | 66 |
(d) Compare A4 and A5; 85>66 , interchange 85 and 66
| 32 | 27 | 51 | 66 | 85 |
Point to be noted: At the end of first pass the largest number 85 has moved to its last position and we applied 4 comparisons to array of 5 elements.It means if we have array of n elements, we need n-1 comparisons in pass 1 , so that largest number can come to its last location.
pass 2:
Now one element is sorted therefor loop will go upto (n-1)th element means 85 is at its exact location we will sort first 4 elements.
(a) Compare first two element A1 and A2; 32 >27, interchange 32 and 27.
| 27 | 33 | 51 | 66 | 85 |
(b) Compare A2 and A3 ; 33<51 , list will not altered
| 27 | 33 | 51 | 66 | 85 |
(c) Compare A3 and A4 ; 51<66,list will not altered
| 27 | 33 | 51 | 66 | 85 |
pass 3:
(a) Compare A1 and A2 ; 27<33 ,list will not altered
| 27 | 33 | 51 | 66 | 85 |
(b) Compare A2 and A3 ; 33<51 , list will not altered
| 27 | 33 | 51 | 66 | 85 |
pass 4:
(a)Compare A1 and A2 ; 27 < 33 ,list will not altered
| 27 | 33 | 51 | 66 | 85 |
Since array A has 5 elements; it is sorted after 3rd pass but loop move n times therefor pass 4 also run.
Complexity
| Best Case | O(n²) |
| Worst Case | O(n²) |