Bubble Sort Program In C Language
Bubble Sort
We use sorting when we want our data ordered in a specific way. To implement this, we use sorting algorithms. Bubble Sort is such a sorting algorithm. It swaps the elements until the elements form the intended order. It compares each element to its adjacent element and keeps swapping untill an element reaches its correct position.
You can learn more about Bubble Sort Algorithm from here.
Algorithm for Bubble Sort Program In C
- We traverse the array and check if the current element is less than or equal to the next element. If yes, we continue traversing the array otherwise we swap the two elements.
- We do the above step array_size - 1 times.
- The result is a sorted array.
Method 1: Bubble Sort Program In C Using nested for loops
In this approach, we use nested for loops to traverse over the array and compare the adjacent elements.
#include <stdio.h>
void bubbleSort(int arr[], int size) {
for (int step = 0; step < size - 1; ++step) {
for (int i = 0; i < size - step - 1; ++i) {
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[10000];
int n;
printf("Enter size of the array: ");
scanf("%d", &n);
printf("Enter the array elements: ");
for(int i = 0; i < n; i++)
scanf("%d", &arr[i]);
bubbleSort(arr, n);
printf("After sorting, the array in ascending order is: ");
printArray(arr, n);
}
Enter size of the array: 5
Enter the array elements: -2 45 32 0 2
After sorting, the array in ascending order is: -2 0 2 32 45
Method 2: Bubble Sort Program In C using nested while loops
This method is very similar to the above method. Here, instead of for loops, we use nested while loops.
#include <stdio.h>
void bubbleSort(int arr[], int size) {
int step = 0;
while(step < size - 1) {
int i = 0;
while(i < size - step - 1) {
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
++i;
}
++step;
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[10000];
int n;
printf("Enter size of the array: ");
scanf("%d", &n);
printf("Enter the array elements: ");
for(int i = 0; i < n; i++)
scanf("%d", &arr[i]);
bubbleSort(arr, n);
printf("After sorting, the array in ascending order is: ");
printArray(arr, n);
}
Enter size of the array: 4
Enter the array elements: 23 12 65 45
After sorting, the array in ascending order is: 12 23 45 65
Method 3: Bubble Sort Program In C using Pointers to swap elements
The algorithm is same as above two approaches but here, instead of swapping elements in the for loop, we pass addresses of the elements to be swapped to a swap function which uses pointers to swap the two elements.
#include <stdio.h>
void swap(int *i, int *j){
int temp;
temp = *i;
*i = *j;
*j = temp;
}
void bubbleSort(int arr[], int size) {
for (int step = 0; step < size - 1; ++step) {
for (int i = 0; i < size - step - 1; ++i) {
if (arr[i] > arr[i + 1]) {
swap(&arr[i], &arr[i + 1]);
}
}
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[10000];
int n;
printf("Enter size of the array: ");
scanf("%d", &n);
printf("Enter the array elements: ");
for(int i = 0; i < n; i++)
scanf("%d", &arr[i]);
bubbleSort(arr, n);
printf("After sorting, the array is: ");
printArray(arr, n);
}
Enter size of the array: 4
Enter the array elements: 3 2 7 5
After sorting, the array in ascending order is: 2 3 5 7
Method 4: Bubble Sort Program In C using Optimized Approach
This approach is a little bit optimized that the others. Here, if the inner loop does not encounter any swapping, we break out of the loop and continue with the next iteration. No swapping means that the array elements are sorted. So we do not need to traverse on them again.
#include <stdio.h>
#include<stdbool.h>
void swap(int *i, int *j){
int temp;
temp = *i;
*i = *j;
*j = temp;
}
void bubbleSort(int arr[], int size) {
bool swapped;
for (int step = 0; step < size - 1; ++step) {
swapped = false;
for (int i = 0; i < size - step - 1; ++i) {
if (arr[i] > arr[i + 1]) {
swap(&arr[i], &arr[i + 1]);
swapped = true;
}
}
if(swapped = false)
break;
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[10000];
int n;
printf("Enter size of the array: ");
scanf("%d", &n);
printf("Enter the array elements: ");
for(int i = 0; i < n; i++)
scanf("%d", &arr[i]);
bubbleSort(arr, n);
printf("After sorting, the array is: ");
printArray(arr, n);
}
Enter size of the array: 7
Enter the array elements: -5 9 2 34 133 95 4
After sorting, the array is: -5 2 4 9 34 95 133
Time Complexity
Best Time:
We get best time complexity in Bubble Sort when the array is already sorted. It is O(n).
Average Time:
The average time complexity is O(\(n^2\)).
Worst Time:
We get worst time complexity when the given array is sorted in descending order. Let us see how we calculate the worst time complexity-
First pass:- Number of comparisons = From i = 0 to i < n - 1 = n - 1
Number of swaps = n - 1
Second pass:- Number of comparisons = From i = 1 to i < n - 1 = n - 2
Number of swaps = n - 2
.
.
.
(n - 1)th pass:- Number of comparisons = From i = n - 2 to i < n - 1 = 1
Number of swaps = 1
Total number of comparisons = (n - 1) + (n - 2) + (n - 3) + . . . + 2 + 1 = \({(n - 1) * (n - 1 + 1)} \over 2\) = \({(n - 1) * n} \over 2\)
Hence, the worst case time complexity of bubble sort is of the order of O(\(n^2\)).
Space Complexity
The algorithm uses O(1) extra space because we only make use of temporary variables to swap elements and no other data structure.
