Bubble Sort in C with Explanation | Algorithm, Program and Complexity

What is Bubble Sort?

It is the basic sorting algorithm to sort array elements. It compares the pair of adjacent elements from an array. If the order is wrong, it just swaps the element.

If there are n-elements in the array, it iterates loop n times. In each iteration, one element is placed in order at the end of in array.

It is not easy to understand this algorithm with words. So, in this post, I will ponder Bubble sort in C with explanation in detail. It will make your understanding clear.

Algorithm Step by step:

• Take the array as input
• For each element (say x) in the array
  • For each adjacent element (say y) to x in the array
    • Compare element x with y.
    • Swap if it is not in order

Bubble Sort in C with Explanation:

How does Bubble sort work?

Let’s take and array of elements 52, 35, 91, 31, 56

Here we want to order it in the ascending order.

Iteration 1:

Keep a pointer to the first element (5) and compare it with 35. As 35 is lower than 52, swap it.

Result array: 35, 52, 91, 31, 56

Increment the pointer to point the second element i.e. 52. Compare it with the 3rd element (91). As 91 is greater than 52, do nothing.

Increment the pointer to point 3rd element (91) compare with the 4th element (31). As 91 is greater than 31, just swap them.

Result array: 35, 52, 31, 91, 56

Again increment the pointer and compare 91 with 56. As 91 is greater than 56, swap them.

Result array: 35, 52, 31, 56, 91

You can see, the largest element has reached the last position.

Iteration 2:

After the second iteration,

Result array: 35, 31, 52, 56, 91

The array is partitioned into two parts; the second half is sorted (mentioned above in bold format).

Note: To optimize the algorithm, you can skip comparing element with the elements from the second half.

Iteration 3:

Result array: 35, 31, 52, 56, 91

Iterate the above steps (n-1) times (until you get a sorted array).

Iteration 4:

Final sorted array: 31, 35, 52, 56, 91

Program:

#include<stdio.h>

void main()
{
	int nArr[]={34, 35, 91, 92, 93};
	int nSize = sizeof(nArr)/sizeof(int);
	int i=0, j=0, t=0;

	//Special Case to reduce complexity in Best Case(O(n))
	int nSorted= 0;		

	printf("\nInput  array: ");
	for(i=0;i<nSize;i++)
		printf("%d ", nArr[i]);
	


	for(i = nSize-1; i>0 && nSorted == 0; i--)
	{
		nSorted = 1;
		for(j=0;j<i;j++)
		{
            if(nArr[j]>nArr[j+1])
			{
				t= nArr[j];
				nArr[j]=nArr[j+1];
				nArr[j+1] = t;
				
				nSorted = 0;
			}
		}
	}

	printf("\nSorted array: ");
	for(i=0;i<nSize;i++)
		printf("%d ", nArr[i]);
}

The output of a program:

Input array: 52, 35, 91, 31, 56
Sorted array: 31, 35, 52, 56, 91

Complexity:

Loops run twice for each element in an array so it takes time O(n^2). 

Let’s take a best case where input array is already sorted. There is no need of swapping element and only one iteration is required. So the best case complexity is  Ω(n).

In average and worst cases, it compares each element to its adjacent element in the array. It requires n iterations. So the average case and worst case complexity are O(n^2).

Worst Case Complexity: O(n^2)

Best Case Complexity: Ω(n)

Average Case Complexity: O(n^2)

Advantages of Bubble Sort:

• The bubble sort algorithm is easy to understand and to implement. Complete code work on two loops. You just have to figure out how does these two loops actually work.
• It does not require any extra space as it is an in-place sorting algorithm.
• It takes on Ω(n) time in the best case.

Disadvantages of Bubble Sort:

• It has a time complexity of O(n^2) in average and worst cases.
• There are so many alternative algorithms which take O(n*log(n)) time for sorting. So bubble sort is slower than most of sorting algorithms.

This is all about bubble sort in C with explanation. If you have any question, please write in a comment.

Other Sorting Algorithm:  Selection Sort in C with Explanation (Algorithm, Program & Time Complexity)