In this article, we will learn about the bubble sort algorithm and see how to implement it step by step in the C programming language. Bubble sort is a foundational algorithm that sorts by continuously swapping neighbouring elements until the entire array is in order. We’ll guide you through a detailed implementation of the Bubble Sort algorithm using the C programming language, ensuring you understand each step and can confidently apply this knowledge in your own projects.
What is Bubble Sort?
Bubble sort is the simplest sorting algorithm that repeatedly steps through the list or array data structure through the list. It compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.
POSTGRADUATE PROGRAM IN
Multi Cloud Architecture & DevOps
Master cloud architecture, DevOps practices, and automation to build scalable, resilient systems.
Bubble Sort Algorithm in C
Let’s see how the bubble sorting algorithm works:
- Run the two loops nested in one another.
- The outer loop will run from i = 0 to i < n -1, where n is the number of elements in the list.
- There is one more loop, which is run on the inner loop j=0 to j < n-i -1. It is because, after each iteration of the outer loop, one element at the end (or at the start if the order is decreasing order) will be in its right place, so we can leave it as is.
- Then, we will check if the arr[j] > arr[j+1]]. If it’s true, then we will swap places of these elements. If this condition is false, we will continue to the next iteration.
- This process will be repeated till the conditions of the loop are not satisfied.
For Decreasing, we have to change this thing in our bubble sort algorithm.
- The inner loop will run from j = i to j < n -1.
- We will compare the elements as arr[j] < arr[j+1].
The following program demonstrates the Bubble Sort Program in C language:
Program
// C program for implementation of Bubble sort
#include <stdio.h>
// swap function in C
void swap(int* arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// A function to implement bubble sort
void bubbleSort_algo(int arr[], int n)
{
int i, j;
for (i = 0; i < n – 1; i++)
for (j = 0; j < n – i – 1; j++) if (arr[j] > arr[j + 1])
swap(arr, j, j + 1);
}
// Function to print an array
void display(int arr[], int size){
int i;
for (i = 0; i < size; i++)
printf(“%d “, arr[i]);
printf(“n”);
}
// Driver code
int main()
{
int arr[] = { 23, 33, 534, 1434 , 2343};
int N = sizeof(arr) / sizeof(arr[0]);
bubbleSort_algo(arr, N);
printf(“Sorted array: “);
display(arr, N);
return 0;
}
Output
Sorted array: 23 33 534 1434 2343
Complexity Analysis of Bubble Sort:
Time Complexity: O(N2), where N is the number of items in the list.
Auxiliary Space: O(1)
Working of Bubble Sort in C
In this section, we will see the Bubble Sort algorithm. Let’s take an unsorted array and sort it using the Bubble Sort Array.
Let’s take the example of an array.
| 13 | 32 | 26 | 35 | 10 |
First Iteration
In the First iteration, we will start with the initial two elements. We will compare them to check whether the first element is greater or not.
| 13 | 32 | 26 | 35 | 10 |
In this array, 32 is greater than the first element of the array, which is 13. So it is already sorted. We don’t need to sort them.
| 13 | 32 | 26 | 35 | 10 |
Here, 26 is smaller than 32. So, we will swap. After swapping new array will look like
| 13 | 26 | 32 | 35 | 19 |
Now, we compare 32 and 35
| 13 | 26 | 32 | 35 | 10 |
Here, 35 is greater than 32. So, no swapping is required in this new sorted array. Let’s compare it to between 35 and 10.
| 13 | 26 | 32 | 35 | 10 |
Let’s move the second interaction in this array.
Second Iteration
The same process will be followed in the second phase.
| 13 | 26 | 32 | 10 | 35 |
| 13 | 26 | 32 | 10 | 32 |
| 13 | 26 | 32 | 10 | 35 |
Here, we see that 10 is smaller than 32. So, swapping will be performed. After swapping, the array will be:
| 13 | 26 | 10 | 32 | 35 |
| 13 | 26 | 10 | 32 | 35 |
Let’s move the third iteration in the loop.
Third Iterations
The same process will be followed for the third iteration in this section.
| 13 | 26 | 10 | 32 | 35 |
| 13 | 26 | 10 | 32 | 35 |
10 is smaller than 26, so I will swap them. After swapping, the array will look like this.
| 13 | 10 | 26 | 32 | 35 |
| 13 | 10 | 26 | 32 | 35 |
| 13 | 10 | 26 | 32 | 35 |
Now. Let’s move to the fourth iteration.
Fourth Iteration
The fourth iteration. The array will look like this
| 10 | 13 | 26 | 32 | 35 |
Here, we don’t need to swap any element. This array is now sorted.
Bubble Sort in C using For Loop
In this section, we will create a bubble sort program using the for loop. We have declared and initialised an array of size 5 with values such as 44, 33, 11, 22, 55, etc. For sorting, we used nested loops and kept checking on adjacent elements of a one-dimensional array.
The following program demonstrates the for loop:
Program
#include <stdio.h>
void bubbleSort(int arr[], int n) {
int i, j;
for (i = 0; i < n – 1; i++) {
for (j = 0; j < n – i – 1; j++) { if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
printf(“Sorted array: n”);
for (int i = 0; i < n; i++)
printf(“%d “, arr[i]);
printf(“n”);
return 0;
}Output
Sorted array:
11 12 22 25 34 64 90
82.9%
of professionals don't believe their degree can help them get ahead at work.
Bubble Sort in C using a while loop
In this section, we will create a bubble Sort program using the while loop in C language. We will now use a while loop to sort the array in ascending order using the Bubble Sort Algorithm.
The following program demonstrates the while loop
Program
#include <stdio.h>
void bubbleSort(int arr[], int n) {
int i = 0;
int swapped = 1;
while (swapped) {
swapped = 0;
int j = 0;
while (j < n – i – 1) { if (arr[j] > arr[j + 1]) {
// Swap arr[j] and arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1;
}
j++;
}
i++;
}
}
void display(int arr[], int length){
for(int i = 0 ;i< length;i++){
printf(“%d “,arr[i]);
}
}
int main() {
int arr[] = {64, 34, 25, 34, 234, 234 } ;
int length = sizeof(arr)/ sizeof(arr[0]);
bubbleSort(arr,length) ;
display(arr,length) ;
return 0 ;
}Output
25 34 34 64 234 234Bubble Sort in C Using Functions
In this section, we will implement the Bubble Sort algorithm using functions. The code of bubble sort is in user-defined functions, which contain the main mechanism.
The following program demonstrates the Bubble Sort in C language.
Program
#include <stdio.h>
void Bubble_sort(int arr[], int n) {
//Bubble sorting function to sort the array
for (int i = 0; i < n – 1; i++) {
for (int j = 0; j < n – i – 1; j++) { if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main() {
int n = 8;
int arr[8] = {33, 343,203, 233, 141, 133, 23, 1343};
Bubble_sort(arr, n);
printf(“Array after implementing Bubble sort: “);
for (int i = 0; i < n; i++) {
printf(“%d “, arr[i]);
}
return 0;
}
Output
Array after implementing Bubble sort: 23 33 133 141 203 233 343 1343
Bubble Sort in C using pointers
In this section, we will implement the Bubble Sort in C language using C pointers. We will use pointers and swap both values from their respective memory locations. In this way, we will be able to sort the array by constantly checking the adjacent elements.
The following program demonstrates the bubble sort in C using pointers
Program
#include <stdio.h>
void Bubble_sort(int *arr, int n) {
for (int i = 0; i < n – 1; i++) {
for (int j = 0; j < n – i – 1; j++) { if ( *(arr + j) > *(arr + j + 1)) {
int temp = *(arr + j);
*(arr + j) = *(arr + j + 1);
*(arr + j + 1) = temp;
}
}
}
printf(“Sorted Array = “);
for (int i = 0; i < n; i++) {
printf(“%d “, *(arr + i));
}
}
int main() {
int n = 5;
int arr[5] = {133, 340, 3430, 5340, 2400};
Bubble_sort(arr, n);
return 0;
}Output
Sorted Array = 133 340 2400 3430 5340
Optimised Implementation of Bubble Sort in C
In this section, we will optimise the previous bubble sort code. If the array is sorted after some passes, it continuously checks (n-1) times, which is not an optimised way of executing an algorithm.
We can optimise the bubble sort algorithm using an additional variable named flag. The flag variable is set to true whenever elements are swapped, reducing the execution time. This is an optimised approach to implementing Bubble sort in the C language.
The following program demonstrates the Bubble Sort in C language:
Program
#include <stdio.h>
#include <stdbool.h>
int main() {
int n = 5;
int arr[5] = {434, 334, 343, 2234, 5343};
for (int i = 0; i < n – 1; i++) {
bool flag = false;
for (int j = 0; j < n – i – 1; j++) { if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = true; //Elements swapped in this pass
}
}
//if flag == false, no swapping is done in this pass
if (flag == false) break; //Array is already sorted, hence break the loop
}
printf(“Sorted Array = “);
for (int i = 0; i < n; i++) {
printf(“%d “, arr[i]);
}
return 0;
}Output
Sorted Array =334 343 434 2234 5343
Conclusion
In this article, we learned about the bubble sort algorithm. It is the simplest algorithm for sorting a list or array. However, it is not very efficient for large data structures. Its complexity is O(n2), meaning its performance decreases drastically as the size of the data increases. However, the bubble sort algorithm can still be useful for educational purposes or for sorting small datasets where simplicity is valued over efficiency.
What is the Bubble Sort algorithm?
How does bubble sort work?
Can bubble sort be optimised?
Is bubble sort stable?
Updated on September 18, 2024