Bubble Sort

Bubble sort is the simplest sorting algorithm that sorts the array by repeatedly swapping the consecutive pair of adjacent elements if they are not sorted.

The Algorithm for Bubble Sort is as follows :

Bubble Sort (A,N)
1.Repeat Step 2 for I=0 to N-1
2.  Repeat for J=0 to N-I
3.    If A[J] > A[J+1]
4.    SWAP A[J] and A[J+1]
5.  [END OF INNER LOOP]
6.[END OF OUTER LOOP]

Let's have a pictorial representation of how bubble sort will sort a given array.

So we see once the first iteration has ended, the largest element has taken its correct place and after second iteration the second largest element will take up its sorted place and it will continue.

It's time to write the code.

   void bubbleSort(int arr[],int n)
    {
     int i, j,temp;

        for(i = 0; i < n-1; i++)
        {
            for (j = 0; j < n-i-1; j++)
            {
                if (arr[j] > arr[j+1])
                 temp=arr[j];
                 arr[j]=arr[j+1];
                 arr[j+1]=temp;
            }
        }           
    }

Consider an array of 6 elements is sorted using the bubble sort algorithm. Even if the array is sorted after second or third iteration, the loop will continue until the 6th iteration. This is merely a waste of time. So, the computer scientists have found out a way to optimize this algorithm by using another variable swapped which will check whether a swapping takes place in the inner for loop. If there are no swapping inside the inner loops, it means array is already sorted and we can jump out of the for loop instead of executing all the iterations.

The optimized implementation of bubble sort algorithm is as follows :

void bubbleSort(int arr[],int n)
        {
         int i, j,temp;
         int swapped=0;

            for(i = 0; i < n-1; i++)
            {
                for (j = 0; j < n-i-1; j++)
                {
                    if (arr[j] > arr[j+1])
                    {
                     temp=arr[j];
                     arr[j]=arr[j+1];
                     arr[j+1]=temp;
                     // if swapping occurs update swapped to 1
                     swapped =1
                     }
                }
                //If the value of swapped is 0 after all the iterations of the inner loop
                //then break out
                if(swapped==0)
                {
                    break;
                }

            }           
        }

Complexity Analysis of Bubble Sort
In bubble sort we have seen there are N-1 comparisons in first pass, N-2 in second pass and so on. Therefore, to compute the complexity of bubble sort, we need to calculate the number of comparisons. It can be shown as follows.

f(n) = (n – 1) + (n – 2) + (n – 3) + ..... + 3 + 2 + 1
f(n) = n (n – 1)/2
f(n) = n^2/2 + O(n) = O(n^2)

The time complexity of the bubble sort algorithm can be summarized as,

• Worst Case Time Complexity [ Big-O ]: O(n^2)
• Best Case Time Complexity [Big-omega]: O(n)
• Average Time Complexity [Big-theta]: O(n^2)

The main advantage of the Bubble sort algorithm is the simplicity of the algorithm.

By going through the above blog post, I am pretty sure that you have gained a sound knowledge on Bubble Sort Algorithm. If you have any queries or need more clarifications, feel free to drop in comments.
Thank You.