Bubble Sort Algo in C - Introduction
Bubble Sort in C is a sorting algorithm where we repeatedly iterate through the array and swap adjacent elements that are unordered. We repeat this until the array is sorted.
As an example, for the array mentioned above - [5, 1, 4, 2, 3] we can see that 5 should not be on the left of 1 and so, we swap them to get: [1, 5, 4, 2, 3]. Next, we see that 5 should again not be on the left of 4. We swap 5 and 4 to get [1, 4, 5, 2, 3]. We repeat this for 5 and 2 and subsequently for 5 and 3 to get [1, 4, 2, 3, 5].
As can be seen - after one “pass” over the array, the largest element (5 in this case) has reached its correct position - extreme right. Let us try to repeat this process.
(1, 4) is correct. However, (4, 2) is an incorrect order. Therefore, we swap 4 and 2 to get [1, 2, 4, 3, 5]. Now again, (4, 3) is incorrect so we do another swap and get [1, 2, 3, 4, 5].
As can be seen, the array is sorted!
This exactly is how bubble sort in C works.
As an example, check this graphic that pictorially depicts how bubble sort works.
Bubble Sort - Explanation
In the first “pass” through the array, the largest element will always get swapped until it is placed to the extreme right. This is because this largest element will always break the desired order. So, at the end of the first pass, the largest element will always reach its correct position.
Now that the largest element has reached its correct position (for instance, 5 reached the last position), we can simply ignore it and concentrate on the rest of the array ([1, 4, 2, 3] in the above case). Here, the largest element in the rest of the array (which is 4) will be nothing but the second largest element in the array. By the above recursive argument, this second largest array will then reach the last position in the remaining array ([1, 2, 3, 4]). This is nothing but a recursive argument on the remaining array.
This continues until for n iterations where n = number of elements in the array. Finally, the array gets sorted.
#include <stdio.h>
void bubble_sort(int a[], int n) {
int i = 0, j = 0, tmp;
for (i = 0; i < n; i++) { // loop n times - 1 per element
for (j = 0; j < n - i - 1; j++) { // last i elements are sorted already
if (a[j] > a[j + 1]) { // swop if order is broken
tmp = a[j];
a[j] = a[j + 1];
a[j + 1] = tmp;
}
}
}
}
int main() {
int a[100], n, i, d, swap;
printf("Enter number of elements in the array:\n");
scanf("%d", &n);
printf("Enter %d integers\n", n);
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
bubble_sort(a, n);
printf("Printing the sorted array:\n");
for (i = 0; i < n; i++)
printf("%d\n", a[i]);
return 0;
}
Bubble Sort Program in C
We loop n times - once for each element of the array. When i = 0, with the j loop, the largest element of the array reaches its correct position. When i = 1, with the j loop, the second largest element of the array reaches its correct position. So on and so forth.
Other Algorithms Merge Sort , Quick Sort , Binary Search
0 Comments