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).