Bubble sort in C

Sorting - Sorting refers to different techniques or methods of arranging or ordering things based on a criteria.
For example - We have list of student names and their age. Sorting techniques can be applied to sort this list based on student's names in decreasing order or in increasing order of their age or vice versa.

Sorting algorithms are the fundamental algorithm problems in computer science. The sorting algorithms are also embedded into other algorithms like search and merge algorithms.

Some of the sorting algorithms are bubble sort, selection sort, insertion sort, heap sort, quick sort, merge sort etc.

Bubble Sort (also known as sinking sort) - This sorting technique probably is the oldest and easiest of all the sorting algorithms. And hence it is also the most inefficient one. It is seldom used in practical applications. Some researchers even have gone to say that this algorithm should not even be taught.

Basic Principle - In this algorithm each element in the list is compared with the next element in the list and swapping the position of two if required. With each iteration (Pass) the largest element in the list is "bubbled" to the end of the list.

C Code (Bubble Sort) -

void BubbleSort (int a[], int a_size)
{
   int i,j,temp;
   for (i < 0; j < a_size - 1; ++i)
   {
      for (j=0; j < a_size - 1 - i; ++j)
      {
         if(a[j] > a[j+1])
           {
             temp = a[j+1];
      a[j+1] = a[j];
             a[j] = temp;
     }
       }
    }
}

Bubble Sort at work -

Suppose we have following list of elements which we need to sort in increasing order.(Will give the values of diffrent variables wherever possible as per above code snippet.)
List - 5 3 7 1 4 9      // a[] = {5,3,7,1,4,9}, a_size = 6

Pass 1 (i=0)

1) 5 3 7 1 4 9 -> 3 5 7 1 4 9   // 5 > 3 hence swapped, i = 0, j = 0, a[j] = 5,  a[j+1] = 3, temp = 3
2) 3 5 7 1 4 9 -> 3 5 7 1 4 9   // 7 > 5 nothing happened, i = 0, j = 1, a[j] = 5, a[j+1] = 7
3) 3 5 7 1 4 9 -> 3 5 1 7 4 9   // 7 > 1 hence swapped,i = 0, j = 2, a[j] = 7, a[j+1] = 1, temp = 1
4) 3 5 1 7 4 9 -> 3 5 1 4 7 9   // 7 > 4 hence swapped, i = 0, j = 3, a[j] = 4, a[j+1] = 1, temp = 4
5) 3 5 1 4 7 9 -> 3 5 1 4 7 9   // 9 > 7 nothing happened, i = 0, j = 4, a[j] = 7, a[j+1] = 9. End of Pass 1. Biggest element 9 is bubbled to the last.

Pass 2 (i=1)

1) 3 5 1 4 7 9 -> 3 5 1 4 7 9   // 5 > 3 nothing happened, i = 1, j = 0, a[j] = 3, a[j+1] = 5
2) 3 5 1 4 7 9 -> 3 1 5 4 7 9   // 5 > 1 hence swapped,i = 1, j = 1, a[j] = 5,  a[j+1] = 1, temp = 1
3) 3 1 5 4 7 9 -> 3 1 4 5 7 9   // 5 > 4 hence swapped,i = 1, j = 2, a[j] = 5,  a[j+1] = 4, temp = 4
4) 3 1 4 5 7 9 -> 3 1 4 5 7 9   // 7 > 5 nothing happened,i = 1, j = 3, a[j] = 5,  a[j+1] = 7, temp = 7.End of pass 2. Second biggest element 7 is bubbled to second last postion.

Pass 3 (i=2)

1) 3 1 4 5 7 9 -> 1 3 4 5 7 9   // 3 > 1 hence swapped, i = 2, j = 0, a[j] = 3, a[j+1] = 1,temp = 1
2) 1 3 4 5 7 9 -> 1 3 4 5 7 9   // 4 > 3 nothing happened,i = 2, j = 1, a[j] = 3, a[j+1] = 4
3) 1 3 4 5 7 9 -> 1 3 4 5 7 9   // 5 > 4 nothing happened,i = 2, j = 2, a[j] = 4, a[j+1] = 5,End of pass 3. Third biggest element 5 is bubbled to third last position.


Pass 4(i=3)

1) 1 3 4 5 7 9 -> 1 3 4 5 7 9   // 3 > 1 nothing happened,i = 3, j = 0, a[j] = 1, a[j+1] = 3
2) 1 3 4 5 7 9 -> 1 3 4 5 7 9   // 4 > 3 nothing happened,i = 3, j = 1, a[j] = 3, a[j+1] = 4,End of pass 4. Fourth biggest element 4 is bubbled to third position.

Pass 5(i=4)

1) 1 3 4 5 7 9 -> 1 3 4 5 7 9   // 3 > 1 nothing happened,i = 4, j = 0, a[j] = 1, a[j+1] = 3,End of pass 5. Fivth biggest element 3 is bubbled to second position.

Issues in Bubble Sort -

As you can see in the example above we need a_size - 1 - i comparison's in every pass (i). So the number of comparisons performed by the bubble sort algorithm can be summed as (n-1)+(n-2)+…….+2+1= n(n-1)/2 = O(n2), here n = number of elements to sort. In the example above this value comes out to be 5+4+3+2+1 = 15. In any case i.e. worst case or the best case number of comparisons remain same i.e. O(n2).

worst case = elements are in decreasing order
best case = elements are in increasing order

Difference in worst and best case is the number of swapes which happen. In worst case we have 0(n2) number of swaps while in best case we do not have any swap of elements in the list.

Note - Efficiency of bubble sort can be improved. One way to do this is to check if the list of elements is already sorted during the execution of algorithm. This can be checked by inserting a flag which will check if if during a pass did any swap of elements happened or not. If not that means list is already sorted, and further execution of paases is not required.

C Code (Improved Bubble Sort) -

void BubbleSort (int a[], int a_size)
{
   int i,j,temp;
   bool sorted = false;
   for (i < 0; (j < a_size - 1) && (!sorted) ; ++i)
   {
    sorted = true;
      for (j=0; j < a_size - 1 - i; ++j)
      {
         if(a[j] > a[j+1])
           {
             temp = a[j+1];
             a[j+1] = a[j];
             a[j] = temp;
      sorted = false;
     }
       }
    }
}