Friday, 21 December 2012

Sorting Algorithms: Bubble Sort


Bubble Sort  |  Running time O(n2)  and Memory O(1)

This algorithm compares two adjacent elements of an array, and swaps them if they are in the wrong order.     
If we have to sort an array of n elements,
- This algorithm makes n-1 passes of the array
- In every pass, it compares each pair of adjacent elements in the unsorted part of the array, and swaps them if they are in the wrong order.
- Thus, each pass "bubbles out" the smallest (or largest) element from the unsorted part of the array.

Algorithm
//bubble sorting in descending order i.e. largest to smallest
for ( i=0; i< n-1; i++ )      //i controls the number of passes
{    
   for( j=0; j< n-i; j++ )
   {    
      if( a[j] < a[j+1])      //using > will change sorting order
      {       //swap
              temp   = a[j];
              a[j]   = a[j+1];
              a[j+1] = temp;
      }
   }
 

Example:
          Array to be sorted  :         1 7 2 8 5 3 9               ( 7 elements)
          Sorting order         :          Descending           (largest to smallest)
                                       :         Sorted part of array


As we can easily see, bubble sort involves multiple swaps in each pass, which means it cannot be used when swapping is a costly action. Also, its complexity O(n2) means that the time taken for sorting increases as the square of the number of elements, meaning it can’t be used for large lists. So, it is not a popular sorting technique.

No comments:

Post a Comment