C sorting: bubble sort versus quicksort

Implement two sorts, count their comparisons, and see why O(n log n) beats O(n²).

#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;
}

Output

bubble: 1 2 3 4 5 6 7 8 9
bubble comparisons: 33
quick : 1 2 3 4 5 6 7 8 9
quick comparisons: 16

Explanation

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.

Quicksort picks a pivot, partitions the array so that smaller elements come before it and larger ones after it, and then sorts the two parts recursively. With a reasonable pivot it takes O(n log n) comparisons on average, though a bad pivot on sorted input can make it O(n²). The example uses the Lomuto partition scheme with the last element as the pivot.

Explore the dry run

Guided walkthroughReady

1#include <stdio.h>

3static long comparisons = 0;

5static void bubble_sort(int *a, int n) {

6 for (int pass = 0; pass < n - 1; pass++) {

7 int swapped = 0;

8 for (int i = 0; i < n - 1 - pass; i++) {

9 comparisons++;

10 if (a[i] > a[i + 1]) {

11 int tmp = a[i];

12 a[i] = a[i + 1];

13 a[i + 1] = tmp;

14 swapped = 1;

15 }

16 }

17 if (!swapped) {

18 break;

19 }

20 }

21}

23static void quick_sort(int *a, int low, int high) {

24 if (low >= high) {

25 return;

26 }

27 int pivot = a[high];

28 int boundary = low;

29 for (int i = low; i < high; i++) {

30 comparisons++;

31 if (a[i] < pivot) {

32 int tmp = a[i];

33 a[i] = a[boundary];

34 a[boundary] = tmp;

35 boundary++;

36 }

37 }

38 int tmp = a[boundary];

39 a[boundary] = a[high];

40 a[high] = tmp;

41 quick_sort(a, low, boundary - 1);

42 quick_sort(a, boundary + 1, high);

43}

45static void show(const char *label, const int *a, int n) {

46 printf("%s:", label);

47 for (int i = 0; i < n; i++) {

48 printf(" %d", a[i]);

49 }

50 printf("\n");

51}

53int main(void) {

54 int one[] = {9, 4, 7, 1, 8, 2, 6, 3, 5};

55 int two[] = {9, 4, 7, 1, 8, 2, 6, 3, 5};

56 int n = 9;

58 comparisons = 0;

59 bubble_sort(one, n);

60 show("bubble", one, n);

61 printf("bubble comparisons: %ld\n", comparisons);

63 comparisons = 0;

64 quick_sort(two, 0, n - 1);

65 show("quick ", two, n);

66 printf("quick comparisons: %ld\n", comparisons);

67 return 0;

68}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
Compare neighbours and swap them if they are out of order.	`—`	—
A pass without any swap means the array is sorted, so the loop ends early.	`—`	—
Without the early exit, 8 + 7 + ... + 1 = 36 comparisons would be needed. The sixth pass makes no swap, so the loop stops after 8 + 7 + 6 + 5 + 4 + 3 = 33.	`—`	bubble: 1 2 3 4 5 6 7 8 9 bubble comparisons: 33
Partition around the last element.	`—`	bubble: 1 2 3 4 5 6 7 8 9 bubble comparisons: 33
Sort the part after the pivot, then the part before it was already sorted by the first call.	`—`	bubble: 1 2 3 4 5 6 7 8 9 bubble comparisons: 33
Quicksort needs only 16 comparisons for the same data.	`—`	bubble: 1 2 3 4 5 6 7 8 9 bubble comparisons: 33 quick : 1 2 3 4 5 6 7 8 9 quick comparisons: 16

Cost and common mistakes

Bubble sort O(n²). Quicksort O(n log n) on average and O(n²) in the worst case.

Quicksort recurses deeply when the pivot is always the smallest or largest element, for example on sorted input with this pivot choice. Random or median-of-three pivots avoid it.
Neither sort here is stable for equal elements. Stability matters when sorting records by one key.
In real programs call qsort from <stdlib.h> instead of writing your own.

Try it yourself

How many comparisons does bubble sort need on an already sorted array of 9 elements?

Reveal answer and reasoning

8 comparisons, because one pass with no swaps proves that the array is sorted.

C sorting: bubble sort versus quicksort

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading