Bubble Sort

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²)