What is Bubble Sort ?

In this sorting algorithm, multiple swapping's take place in one pass. Smaller elements move or ‘bubble’ up to the top of the list, hence the name given to the algorithm.

In this method, adjacent members of the list to be sorted are compared. If the item on top is greater than the item immediately below it, then they are swapped. This process is carried on till the list is sorted.

The detailed algorithm follows:

Algorithm: BUBBLE SORT
1. Begin
2. Read the n elements
3. for i=1 to n
for j=n downto i+1
if a[j] <= a[j-1]
swap(a[j],a[j-1])
End // of Bubble Sort

Total number of comparisons in Bubble sort :
= (N-1) +(N-2) . . . + 2 + 1
= (N-1)*N / 2 =O(N^2)

This inefficiency is due to the fact that an item moves only to the next position in each pass.