Bubble Sort

Bubble Sort

Bubble sort is a simple sorting algorithm. This sorting algorithm is comparison-based algorithm in which each pair of adjacent elements is compared and the elements are swapped if they are not in order. This algorithm is not suitable for large data sets as its average and worst case complexity are of Ο(n2) where n is the number of items.

How bubble sort works ?

9    25    18    29    2

Bubble sort starts with very first two elements, comparing them to check which one is greater.

9    25    18    29    2

In this case, value 25 is greater than 9, so it is already in sorted locations. Next, we compare 25 with 18.

9    25    18    29    2

We find that 18 is lower than 25 and these two values must be swapped.

9    18    25    29    2

Next we compare 25 and 29. We find that both are in already true positions.

9    18    25    29    2

Then we move to the next two values, 29 and 2

We know then that 10 is smaller 35. So, we swapped.

9    18    25    2    29

After the last iteration, it should look like this

2    9    18    25    29

Algorithm

begin BubbleSort(list)

for all elements of list

      if list[i] > list[i+1]

         swap(list[i], list[i+1])

      end if

   end for

    return list

   end BubbleSort

Pseudocode

procedure bubbleSort( list : array of items )

loop = list.count;

   for i = 0 to loop-1 do:

      swapped = false

  for j = 0 to loop-1 do:  /* compare the adjacent elements */  

         if list[j] > list[j+1] then /* swap them */

            swap( list[j], list[j+1] )                       

            swapped = true

         end if

         end for

         if(not swapped) then

         break

      end if

       end for

  

end procedure return list