Bubble Sort Algorithm

	Bubble sort is the simplest algorithm which compares two elements at a time and swaps them if they are in wrong order or if first element is greater than the second element. it repeatedly swaps elements until no swap is needed.
	It is not normally used in practice except in School for the purpose of or to know how the sorting algorithm.
	It is not much efficient sorting algorithm as others.
	The complexity of Bubble Sort is О(n²) and it should not be used when n is large.

Example:

A array of  elements: {4,2,3,1,6}

Pass 1:

    {4,2,3,1,6} => {2,4,3,1,6}
    {2,4,3,1,6} => {2,3,4,1,6}
    {2,3,4,1,6} => {2,3,1,4,6}
    {2,3,1,4,6} => {2,3,1,4,6}

Pass 2:

    {2,3,1,4,6} => {2,3,1,4,6}
    {2,3,1,4,6} => {2,1,3,4,6}
    {2,1,3,4,6} => {2,1,3,4,6}
    {2,1,3,4,6} => {2,1,3,4,6}

Pass 3:

    {2,1,3,4,6} => {1,2,3,4,6}
    {1,2,3,4,6} => {1,2,3,4,6}
    {1,2,3,4,6} => {1,2,3,4,6}
    {1,2,3,4,6} => {1,2,3,4,6}

Now array is in sorted order but algorithm does not know about it and one more pass will be run

Pass 4:

    {1,2,3,4,6} => {1,2,3,4,6}
    {1,2,3,4,6} => {1,2,3,4,6}
    {1,2,3,4,6} => {1,2,3,4,6}
    {1,2,3,4,6} => {1,2,3,4,6}

Pseudocode:

   1: procedure BubbleSort( A : list of sortable items ) defined as:

   2:   do

   3:     swapped := false

   4:     for each i in 0 to length( A ) - 1 do:

   5:       if A[ i ] > A[ i + 1 ] then

   6:         swap( A[ i ], A[ i + 1 ] )

   7:         swapped := true

   8:       end if

   9:     end for

  10:   while swapped

  11: end procedure

  12:  

Optimized Pseudocode:

One thing note down to optimize this, after first pass the  n^th element will be at its proper place hundred percent because in each pass the largest element goes down at the last position and swaps will be performed for the remaining n-1 elements in the next pass. so we need to drop last element after each pass to reduce this overhead.

   1: procedure bubbleSort( A : list of sortable items ) defined as:

   2:   n := length( A )

   3:   do

   4:     swapped := false

   5:     n := n - 1

   6:     for each i in 0 to n  do:

   7:       if A[ i ] > A[ i + 1 ] then

   8:         swap( A[ i ], A[ i + 1 ] )

   9:         swapped := true

  10:       end if

  11:     end for

  12:   while swapped

  13: end procedure

  14:  

Implementation in C#:

   1: public int[] BubbleSort(int[] array) 

   2:         {

   3:             bool swap;

   4:             int length = array.Length;

   5:             do

   6:             {

   7:                 swap = false;

   8:                 length = length - 1;

   9:                 for (int j = 0; j < length; j++)

  10:                 {

  11:                     if (array[j] > array[j + 1])

  12:                     {

  13:                         array[j] = array[j] + array[j + 1];

  14:                         array[j + 1] = array[j] - array[j + 1];

  15:                         array[j] = array[j] - array[j + 1];

  16:                         swap = true;

  17:                     }                    

  18:                 }

  19:             }

  20:             while (swap);                         

  21:             return array;

  22:         }

Technorati Tags: Algorithm,C#,Sorting,Bubble Sort

Wikipedia Tags: Algorithm, C#, Sorting, Bubble Sort

Good Luck