Bubble Sort Algorithm Simply Explained

Here we are going to learn about Bubble Sort Algorithm. It is the simplest sorting algorithm. Using this sorting technique, we can sort the elements in ascending or descending order according to our choice. 

It compares two adjacent elements and swaps them if they are not in desired order. This process repeats until all the elements are in desired order.

Lets see how bubble sort algorithm actually works

Suppose we have an array having 5 elements,

int a[5]={ 3, 5, 7, 2, 4 }

Pass 1:

Bubble Sort always start with first two elements, 

Here since 3<5 so no swapping required.

Here also since 5<7 no swapping required.

Here since 7>2, so swapped.

Here since 7>4, so swapped.

Pass 2:

Now, in this iteration we will check upto second last element since the last element is the largest one and have got its position, so there is no need of checking the last element again. 

Here since 3<5, so no swapping is required.

Here since 5>2 so swapped.

Here since 5>4, so swapped.

Pass 3: 

Now, in this iteration we will check upto third element as the last two elements have got their position. So no need of checking them again.

Since 3>2, so swapped.

Since 3<4, so no swapping is required.

Pass 4: 

Now, in this iteration we will only check first two positions as the rest of the elements have already got their position. So no need of checking them again.

Here since 2<3, so no swapping is required.

So we have sorted all the elements in ascending order using Bubble Sort Algorithm.

Approach for writing code-

Run a nested for loop. Say outer loop variable is i and inner loop variable is j.

Compare two adjacent elements i.e., whether a[j+1] > a[j]. If true then swap else move on. Atlast print the sorted array.

Now lets see the code of Bubble Sort in C.

C Program to Sort Elements using Bubble Sort -

#include <stdio.h>

int main(){
    int n;
    printf("Enter number of elements: ");
    scanf("%d",&n);
    int a[n];
    for(int i=0; i<n;i++){
        scanf("%d",&a[i]);
    }
    for (int i=0; i<n-1; i++){
        for(int j=0;j<n-i-1; j++){
            if(a[j+1]<a[j]){
                int t=a[j];
                a[j]=a[j+1];
                a[j+1]=t;
            }
         }
     }
     for(int i=0; i<n; i++){
         printf("%d ",a[i]);
     }
     return 0;
}

Output -

Enter number of elements: 5
3
4
2
7
1
1 2 3 4 7 

Time Complexity: O(N^2)

---

There is one disadvantage of the above code that it always runs in O(N^2) time even of the array is already in sorted form. This increases the execution time.

We can reduce the execution time by optimizing the above code to stop the algorithm if no swapping occurs in the inner loop.

Optimized Bubble Sort Code in C-

#include <stdio.h>

int main(){
    int n;
    int c=0;
    printf("Enter number of elements: ");
    scanf("%d",&n);
    int a[n];
    for(int i=0; i<n;i++){
        scanf("%d",&a[i]);
    }
    for (int i=0; i<n-1; i++){
        for(int j=0;j<n-i-1; j++){
            if(a[j+1]<a[j]){
                int t=a[j];
                a[j]=a[j+1];
                a[j+1]=t;
                c++;
            }
         }
         if (c==0){
            break;
         }
     }
     for(int i=0; i<n; i++){
         printf("%d ",a[i]);
     }
     return 0;
}

Output -

Enter number of elements: 5
3
4
2
7
1
1 2 3 4 7 

In the above code, we have introduced a new variable c, which is initialized with 0. We are increasing the value of c by 1 if swapping occurs, otherwise its value remains 0.

After each iteration, we are checking the value of c if c remains 0 which means elements are already sorted and there is no need of further iterations. 

Time Complexity: O(N)

Best Case Time Complexity: O(N)

Worst Case Time Complexity: O(N^2)