Bubble Sort in C

Bubble Sort is a foundational algorithm that sorts by continuously swapping neighboring elements until the entire array is in order. While it serves as an essential educational tool and is effective for modest data sets, its efficiency diminishes with larger arrays due to its inherent time complexity O(n2). In this context, we'll explore a detailed implementation of Bubble Sort using the C programming language.

Bubble Sort Algorithm in C

Pseudo-code for Bubble Sort in C

As we know, Bubble sort in C works by comparing and swapping adjacent elements in an array.

The above pseudo-code for Bubble sort algorithm in C takes in an array as an argument and then returns sorted array at the end.

To understand it in a better way, let's illustrate it using a step-by-step method:

Assuming we want to sort an array in ascending order and let’s name it arr with n elements in it. Now, this is how the Bubble sort algorithm in C will work:

STEP 1: Starting at index zero, compare the elements with their next ones (arr[0] & arr[1]), and swap if ($arr[0] > arr[1]$). After that compare arr[1] & arr[2] and swap if $arr[1] > arr[2]$. Repeat this process until the end of the array.

After that, the largest element of the array will be present at the end index. This is known as the first pass. We have processed the array elements from $[0 : n-1]$ in this first pass.

STEP 2: Repeat STEP 1 but process array elements from $[0 : n-2]$ because the last element arr[n-1] is already present at its correct position. After this, the largest two elements are present at the end. Basically, for an ith pass, we will traverse array elements till (n-i)th index because i elements from the last are already sorted in their places.

STEP 3: Repeat this process n-1 times to finally get the sorted array in the end. As we are getting the largest respective element at the (n - i)th index each time, there is no need to iterate through the array for n th pass as the first element will be the smallest element of the array already placed.

For instance, if we pass an array consisting of the elements: (5, 3, 8, 4, 6), then the final array after the bubble sort implementation will be: (3, 4, 5, 6, 8).

As we can see in this image, all the adjacent elements are compared and swapped to maintain the ascending order of occurrence, and with this, we always get the largest element of the array at the end index in the first pass.

First Pass: $5\: 3\: 8\: 4\: 6\: \longrightarrow 3\: 5\: 4\: 6\: 8$

Second Pass: $3\: 5\: 4\: 6\: 8\: \longrightarrow3\: 4\: 5\: 6\: 8$

Clearly, after the second pass, our array is sorted. This is fascinating and to understand it's working, we will now study different ways of writing code and implementing the Bubble Sort algorithm in C.

Bubble Sort in C Using For Loop

In this C program, we have implemented Bubble sort using for loop, and to start with, we have declared and initialized an array of size 5 with values: ${44\:,33\:,11\:,22\:,55}$. Then we used nested for loops and kept checking on adjacent elements of a one-dimensional array.

If the left element of $(index\: j)$ is greater than the right element of $(index\: j+1)$, then we swap both the elements from their respective indices.

By doing this, we would always get the largest element of the array at the end index after the first pass. In this way, we would get the sorted array at the end.

Output:

First Pass: $44,\: 33,\: 11,\: 22,\: 55\longrightarrow 33,\: 11,\: 22,\: 44,\: 55$

Second Pass: $33,\: 11,\: 22,\: 44,\: 55\longrightarrow 11,\: 22,\: 33,\: 44,\: 55$

Though our array is sorted after two passes, it will continue checking (n-1) times which is obviously not an optimized approach.

Bubble Sort in C Using While Loop

In this C program, we will be doing exactly the same thing as in our last C program, and the only difference will be that instead of for loop, we will now use while loop to sort the array in ascending order using Bubble sort.

Output:

First Pass: $20,\: 40,\: 10,\: 25,\: 44\longrightarrow 20,\: 10,\: 25,\: 40,\: 44$

Second Pass: $20,\: 10,\: 25,\: 40,\: 44\longrightarrow 10,\: 20,\: 25,\: 40,\: 44$

Bubble Sort in C Using Functions

In this C program, we will implement Bubble sort algorithm using functions. Bubble_sort is a user-defined function which contains the main mechanism (algorithm) of performing Bubble Sort to sort the array in ascending order. Starting with, we have initialized and declared an array of size 8 with elements: ${77,\:55,\:20,\:23,\:11,\:3,\:2,\:1}$.

Then we made a function called passing array and size as parameters which will use the Bubble sort algorithm to sort the array in ascending order.

Output:

First Pass: $77,\: 55,\: 20,\: 23,\: 11,\: 3,\: 2,\: 1\longrightarrow 55,\: 20,\: 23,\: 11,\: 3,\: 2,\: 1,\: 77$

Second Pass: $55,\: 20,\: 23,\: 11,\: 3,\: 2,\: 1,\: 77\longrightarrow 20,\: 23,\: 11,\: 3,\: 2,\: 1,\: 55,\: 77$

Third Pass: $20,\: 23,\: 11,\: 3,\: 2,\: 1,\: 55,\: 77\longrightarrow 20,\: 11,\: 3,\: 2,\: 1,\: 23,\: 55,\: 77$

Fourth Pass: $20,\: 11,\: 3,\: 2,\: 1,\: 23,\: 55,\: 77\longrightarrow 11,\: 3,\: 2,\: 1,\: 20,\ 23,\: 55,\: 77$

Fifth Pass: $11,\: 3,\: 2,\: 1,\: 20,\: 23,\: 55,\: 77\longrightarrow 3,\: 2,\: 1,\: 11,\: 20,\: 23,\: 55,\: 77$

Sixth Pass: $3,\: 2,\: 1,\: 11,\: 20,\: 23,: 55,\: 77\longrightarrow 2,\ 1, 3, 11,\: 20,\: 23,\: 55,\: 77$

Seventh Pass: $2,\: 1,\: 3,\: 11,\: 20,\: 23,\: 55,\: 77\longrightarrow 1,\: 2,\: 3,\: 11,\: 20,\: 23,\: 55,\: 77$

In this example, our array is sorted after 7 passes, i.e. (n-1) times.

Bubble Sort in C Using Pointers

In this C program, we will use pointers alongside user-defined functions i.e., Bubble_sort to implement the Bubble sort algorithm. We will pass an array as a pointer to the first element of the array itself in the Bubble_sort function.

We will use pointers and swap both the values from their respective memory locations. In this way, we will be able to sort the array by constantly checking adjacent elements, and if left-element > right-element, we will just swap them from their memory locations.

Output:

First Pass: $100,\: 400,\: 200,\: 500,\: 300\longrightarrow 100,\: 200,\: 400,\: 300,\: 500$

Second Pass: $100,\: 200,\: 400,\: 300,\: 500\longrightarrow 100,\: 200,\: 300,\: 400,\: 500$

Though our array is sorted after two passes, it will continue checking (n-1) times which is obviously not an optimized approach. Now, we will be looking at an optimized approach to writing a Bubble sort algorithm with best-case time complexity.

Optimized Implementation of Bubble Sort in C

As we have observed in the above example codes, even if the array is sorted after some passes, it continues to check (n-1) times which is not an optimized way of executing an algorithm.

We can reduce the execution time by optimizing the algorithm so that it will have best-case time complexity of O(n) when the array is sorted.

All we have to do is just add an additional variable named flag having boolean value as false initially before each pass.

The flag variable is set as true whenever the swapping of elements has occurred (indicating change of elements from their respective indices); otherwise, it remains false.

On checking if the value of flag is false, it will be understood that the array has been sorted, and it will break out of the loop.

This will definitely reduce the execution time and hence, it is an optimized approach to implementing Bubble sort in C.

Output:

First Pass: $44,\: 33,\: 11,\: 22,\: 55\longrightarrow 33,\: 11,\: 22,\: 44,\: 55$

Second Pass: $33,\: 11,\: 22,\: 44,\: 55\longrightarrow 11,\: 22,\: 33,\: 44,\: 55$

Now here, as we can see, we have our sorted array after two passes, and hence, it breaks out from the loop in the third pass when there will be no swapping between the elements.

Complexity of Bubble Sort in C

Time Complexity

• Worst-Case Time Complexity $\rightarrow$ If all the array elements are in descending order and we need to sort them in ascending order, it is the worst case, and its time complexity will be $O(n^2)$.
• Average-Case Time Complexity $\rightarrow$ This is any general case where elements are in randomly shuffled order and hence, its time complexity will be $O(n^2)$.
• Best-Case Time Complexity $\rightarrow$ This is the case where all the elements of an array are either already placed in a sorted manner, and no swapping is required or when we are implementing the optimized approach of Bubble sort in C. The time complexity is O(n).

Space Complexity

• Space complexity for the standard Bubble sort algorithm is O(1) as there is only one additional variable required to hold the values of swapped elements temporarily.