C sorting: bubble sort versus quicksort
Bubble sort repeatedly steps through the array, swapping adjacent elements that are out of order. After each pass the largest remaining element has bubbled to the end. If a pass makes no swap, the array is sorted and the loop can stop, which makes it fast on sorted input. In general it takes O(n²) comparisons.
C
#include <stdio.h>
static long comparisons = 0;
static void bubble_sort(int *a, int n) {
for (int pass = 0; pass < n - 1; pass++) {
int swapped = 0;
for (int i = 0; i < n - 1 - pass; i++) {
comparisons++;
if (a[i] > a[i + 1]) {
int tmp = a[i];
a[i] = a[i + 1];
a[i + 1] = tmp;
swapped = 1;
}
}
if (!swapped) {
break;
}
}
}
static void quick_sort(int *a, int low, int high) {
if (low >= high) {
return;
}
int pivot = a[high];
int boundary = low;
for (int i = low; i < high; i++) {
comparisons++;
if (a[i] < pivot) {
int tmp = a[i];
a[i] = a[boundary];
a[boundary] = tmp;
boundary++;
}
}
int tmp = a[boundary];
a[boundary] = a[high];
a[high] = tmp;
quick_sort(a, low, boundary - 1);
quick_sort(a, boundary + 1, high);
}
static void show(const char *label, const int *a, int n) {
printf("%s:", label);
for (int i = 0; i < n; i++) {
printf(" %d", a[i]);
}
printf("\n");
}
int main(void) {
int one[] = {9, 4, 7, 1, 8, 2, 6, 3, 5};
int two[] = {9, 4, 7, 1, 8, 2, 6, 3, 5};
int n = 9;
comparisons = 0;
bubble_sort(one, n);
show("bubble", one, n);
printf("bubble comparisons: %ld\n", comparisons);
comparisons = 0;
quick_sort(two, 0, n - 1);
show("quick ", two, n);
printf("quick comparisons: %ld\n", comparisons);
return 0;
}