Bubble Sort is a straightforward sorting algorithm that operates by repetitively stepping through a list, comparing all pairs of adjacent items and swapping them if they follow an incorrect order. The pass through the list is repeated until no more swaps are needed, indicating that the list is sorted.
The Bubble Sort algorithm can be implemented in C programming in multiple ways, but the basic concept remains the same. Elements of the list are compared with each other in pairs, starting from the beginning of the list. If the first element of the pair is greater than the second, the positions of the elements are swapped. This process is repeated until the entire list is sorted.
Bubble sort works by making multiple passes over a list, comparing and swapping elements, and then repeating the process until the list is sorted.
Let's take an example: Suppose we have the list [5, 3, 8, 4, 2].
In the first pass, Bubble sort starts at the first pair of elements, 5 and 3. It compares the two numbers; since 5 is greater than 3, it swaps them. The list looks like [3, 5, 8, 4, 2].
Next, it compares 5 and 8; since 5 is not greater than 8, it doesn't swap them.
Then it compares 8 and 4 and swaps them because 8 is greater than 4. The list looks like [3, 5, 4, 8, 2].
It repeats the same process for 8 and 2, resulting in [3, 5, 4, 2, 8].
After the first pass, we can see that the largest number, 8, has moved to the correct position at the end of the list.
The process repeats for the remaining elements until the entire list is sorted.
The Bubble Sort algorithm can be implemented in C programming using loops such as for and while, functions, or pointers. The algorithm remains the same; only the implementation varies.
In C, we use a nested loop where the outer loop runs from the beginning of the array to the end, and the inner loop runs from the beginning of the array to the last unsorted element. They are swapped; if the current element in the inner loop is greater than the next element.
for(int l = 0; x < n-1; m++) {
for(int m = 0; m < n-i-1; m++) {
if(array[m] > array[m+1]) {
// Swap array[m] and array[m+1]
int temp = array[m];
array[m] = array[m+1];
array[m+1] = temp;
}
}
} |
Here, n is the number of elements in the array arr[]. This code will sort the array in ascending order.
Here's a full implementation of Bubble Sort using a for loop in C:
#include <stdio.h>
void bubbleSort(int array[], int n) {
for(int l = 0; l < n-1; l++) {
for(int m = 0; m < n-1; m++) {
if(array[m] > array[m+1]) {
// Swap array[m] and array[jm+1]
int temp = array[m];
array[m] = array[m+1];
array[m+1] = temp;
}
}
}
}
void printArray(int array[], int size) {
for (int l = 0; l < size; l++)
printf("%d ", array[l]);
printf("\n");
}
int main() {
int array[] = {46, 34, 25, 23, 22, 11, 90};
int n = sizeof(array) / sizeof(array[0]);
bubbleSort(array, n);
printf("Sorted array: \n");
printArray(array, n);
return 0;
} |
In this program, we define the bubbleSort() function, which performs the sorting operation. Inside the bubbleSort() function, we use a nested for loop to repeatedly iterate over the array, comparing and swapping elements as necessary.
The printArray() function prints the elements of the array. It's used to display the array before and after sorting.
The main() function is where our program begins execution. The array arr[] to be sorted is defined here, and the bubbleSort() function is called to sort this array. The sorted array is then printed on the screen.
Using a while loop, we can also implement the Bubble Sort algorithm. Here is a simple program for that:
#include <stdio.h>
void bubbleSort(int array[], int n) {
int l = n-1;
while(l > 0) {
int m = 0;
while(m < l) {
if(array[m] > array[m+1]) {
// Swap array[m] and array[m+1]
int temp = array[m];
array[m] = array[m+1];
array[m+1] = temp;
}
m++;
}
l--;
}
}
void printArray(int array[], int size) {
for (int l = 0; l < size; l++)
printf("%d ", array[l]);
printf("\n");
}
int main() {
int array[] = {49, 34, 55, 12, 22, 61, 90};
int n = sizeof(array) / sizeof(array[0]);
bubbleSort(array, n);
printf("Sorted array: \n");
printArray(array, n);
return 0;
} |
This program works similarly to the previous one, with the difference being that we are using a while loop to control the flow of our program instead of a for loop.
Functions allow us to modularise our code. Here is a bubble sort program in C using function.
#include <stdio.h>
void swap(int *xp, int *yp) {
int temp = *xp;
*xp = *yp;
*yp = temp;
}
void bubbleSort(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]) {
swap(&arr[j], &arr[j+1]);
}
}
}
}
void printArray(int arr[], int size) {
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
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");
printArray(arr, n);
return 0;
} |
Here, we've defined a function swap() that takes two pointers and swaps the values they point to. This function is used in the bubbleSort() function to swap the elements of the array if they are in the wrong order.
We can also implement Bubble Sort using pointers. Here's an example of how we can do that:
#include <stdio.h>
void swap(int *ip, int *jp) {
int temp = *ip;
*ip = *jp;
*jp = temp;
}
void bubbleSort(int *array, int n) {
for(int l = 0; l < n-1; l++) {
for(int m = 0; m < n-l-1; m++) {
if(*(array+m) > *(array+m+1)) {
swap((array+m), (array+m+1));
}
}
}
}
void printArray(int *array, int size) {
for (int l = 0; l < size; l++)
printf("%d ", *(array + l));
printf("\n");
}
int main() {
int array[] = {64, 47, 25, 28, 22, 17, 90};
int n = sizeof(array)/sizeof(array[0]);
bubbleSort(array, n);
printf("Sorted array: \n");
printArray(array, n);
return 0;
} |
In this code, we use pointers to access the array elements. In the bubbleSort() and printArray() functions, the array argument is replaced by a pointer to the first element of the array. We then use pointer arithmetic to access the elements of the array.
In the standard implementation of Bubble Sort, the algorithm doesn't stop even if the array is sorted before all the iterations are completed. This can lead to unnecessary operations. An optimised version of Bubble Sort introduces a flag to check whether any swapping occurred in the previous pass. If no swaps occur, the array is already sorted, and the algorithm can terminate early. Here's how it's implemented:
#include <stdio.h>
#include <stdbool.h>
void swap(int *ip, int *jp) {
int temp = *ip;
*ip = *jp;
*jp = temp;
}
void bubbleSort(int array[], int n) {
int l, m;
bool swapped;
for(l = 0; l < n-1; l++) {
swapped = false;
for(m = 0; m < n-l-1; m++) {
if(array[m] > array[m+1]) {
swap(&array[m], &array[m+1]);
swapped = true;
}
}
// If no two elements were swapped by inner loop, then break
if(swapped == false) {
break;
}
}
}
void printArray(int array[], int size) {
int l;
for(l = 0; l < size; l++)
printf("%d ", array[l]);
printf("\n");
}
int main() {
int array[] = {48, 34, 57, 28, 21, 31, 90};
int n = sizeof(array) / sizeof(array[0]);
bubbleSort(array, n);
printf("Sorted array: \n");
printArray(array, n);
return 0;
} |
In this optimised version, we introduce a boolean variable swapped to check if any swap happened in the current iteration. If no swap occurs in the inner loop, the swapped flag remains false, which indicates that the array is already sorted and breaks the outer loop early, thereby optimising the algorithm.
The standard Bubble Sort algorithm can be optimised by introducing a flag that checks if any swap has happened in the last pass. If the flag is false after a pass, it implies the array is sorted, and there is no need for further passes.
Here’s a proper pseudocode that you can look at to understand how optimized bubble sort algorithm should work:
bubbleSort(array[], n)
for l from 0 to n-1 do:
swapped = false
for m from 0 to n-l-1 do:
if array[m] > array[m+1] then:
swap array[m] and array[m+1]
swapped = true
if not swapped then:
break
The Bubble Sort algorithm, despite its simplicity, isn't the most efficient for large datasets. Here's why:
Worst-case time complexity: O(n^2)
Average-case time complexity: O(n^2)
Best-case time complexity: O(n)
Space complexity: O(1)
The Bubble sort time complexity in the best-case scenario, where the input is already sorted, is O(n) because Bubble Sort only makes one pass over the data in this case. But in the average and worst-case scenarios, Bubble Sort must make multiple passes over the data, leading to a time complexity of O(n^2). The space complexity is O(1) because Bubble Sort is an in-place sorting algorithm.
Despite being inefficient for larger datasets, Bubble Sort is straightforward to understand and easy to implement, making it suitable for:
Educational purposes: Due to its simplicity, it's often used in education for teaching sorting algorithms.
Small datasets: For small arrays or lists, Bubble Sort can be more efficient and faster compared to more complex algorithms.
Nearly sorted data: If you have a list that's already mostly sorted with just a few elements out of place, Bubble Sort can be very efficient.
While Bubble Sort is simple and easy to implement, its inefficiency for larger data sets can be a disadvantage. In such cases, other sorting algorithms might be more suitable:
Selection Sort in C: Selection Sort segments the input into a sorted and an unsorted region. It repetitively chooses the largest or smallest (based on the ordering) element from the unsorted region and moves it to the sorted region.
Insertion Sort in C: Insertion Sort is another simple and intuitive sorting algorithm, it builds the final sorted array one item at a time. It is significantly less effective on expansive lists when compared to more advanced algorithms like heap sort, merge sort or quick sort.
The worst-case scenario for Bubble Sort occurs when the array is sorted in reverse order. In such a case, Bubble Sort would need to make n*(n-1)/2 comparisons and swaps, where n is the number of elements in the array. This leads to a worst-case time complexity of O(n^2). The space complexity remains O(1) as only a single extra space is required for the temporary variable used in swapping.
Bubble Sort is a straightforward sorting algorithm that may not be efficient for large datasets due to its time complexity. However, it has merits in certain situations. Its simplicity, in-place sorting, and stability make it useful for nearly sorted lists or smaller datasets.
If you're interested in algorithms like Bubble Sort and want to further explore computer science and programming, consider checking out upGrad's comprehensive Executive PG Program in Software Development from IIIT-B. The program offers an immersive learning experience, helping development aspirants to gain can hands-on experience to boost their careers.
1. How does bubble sort work?
Bubble sort works by consistently swapping the adjacent elements if they are following an incorrect order. The algorithm continues to iterate through the list until it can traverse the entire list without swapping any elements.
2. Is bubble sort efficient?
Bubble sort is simple and suitable for small datasets or nearly sorted lists. However, it is inefficient for larger datasets with a worst-case and average time complexity of O(n^2). There are other more efficient sorting algorithms for handling larger datasets, like QuickSort, MergeSort, and HeapSort.
3. When should bubble sort be used?
Bubble sort is best used when dealing with a small dataset or a list nearly sorted. It can also be a good choice for educational purposes due to its simplicity.
Leave a Reply
Your email address will not be published. Required fields are marked *