Bubble sort in C is a simple sorting algorithm that sorts the elements in ascending and descending order. It repeatedly compares the adjacent elements and swaps them if they are in the wrong order.
Example to understand Bubble Sort in C,
Suppose there is an array that contains ” 5 1 4 2 8″. If you want to sort this array in ascending order (lowest number to the greatest number), you need to take the following steps,
First Pass:
( 5 1 4 2 8 ) → ( 1 5 4 2 8 ), Here, the algorithm compares the first two elements and swaps since 5 > 1.
( 1 5 4 2 8 ) → ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) → ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) → ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), the algorithm does not swap them.
Second Pass:
( 1 4 2 5 8 ) → ( 1 4 2 5 8 )
( 1 4 2 5 8 ) → ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
Third Pass:
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
Following is the implementation of Bubble Sort in C.
#include <stdio.h> #define ARRAY_SIZE(x) sizeof(x)/sizeof(x[0]) //Function to swap element void Swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } //Function to sort the array void BubbleSort(int *arr, int n) { int i = 0, j = 0; for (i = 0; i < n-1; i++) { for (j = 0; j < n-i-1; j++) { if (arr[j] > arr[j+1]) { Swap(&arr[j], &arr[j+1]); } } } } int main() { int i = 0; //Array int arr[] = {6,5,3,1,8,7,2,4}; //Get array size int n = ARRAY_SIZE(arr); //Function to sort array in ascending order BubbleSort(arr, n); printf("Array in ascending order: \n"); //Print array for (i=0; i < n; i++) { printf("%d ", arr[i]); } return 0; }
Output: Array in ascending order: 1 2 3 4 5 6 7 8
Optimized Implementation of bubble sort:
The above-implemented code for bubble sort always runs O(n^2) time even if the array is sorted. It can be optimized by stopping the algorithm if there is no swapping occur in the inner loop.
#include <stdio.h> #define ARRAY_SIZE(x) sizeof(x)/sizeof(x[0]) //Function to swap element void Swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } //Function to sort the array void BubbleSort(int *arr, int n) { int i = 0, j = 0; int swapflag = 0; for (i = 0; i < n-1; i++) { swapflag = 0; for (j = 0; j < n-i-1; j++) { if (arr[j] > arr[j+1]) { Swap(&arr[j], &arr[j+1]); swapflag = 1; } } //If inner loop not executed, break the loop if (swapflag == 0) break; } } int main() { int i = 0; //Array int arr[] = {6,5,3,1,8,7,2,4}; //Get array size int n = ARRAY_SIZE(arr); //Function to sort array in ascending order BubbleSort(arr, n); printf("Array in ascending order: \n"); //Print array for (i=0; i < n; i++) { printf("%d ", arr[i]); } return 0; }
Output: Array in ascending order: 1 2 3 4 5 6 7 8
Important characteristics of Bubble Sort:
- The best time complexity for Bubble Sort is O(n).
- The average and worst time complexity is O(n²).
- The space complexity for Bubble Sort is O(1).