Bubble Sort

Overview

Property	Value
Best Case	$\Omega (n^2)$
Worst Case	$O(n^2)$
Avg. Case	$O(n^2)$
Aux. Memory	$O(1)$
Stable	Yes
Adaptive	Yes

void swap(int i, int j, int *A) {
  int tmp = A[i];
  A[i] = A[j];
  A[j] = tmp;
}
 
void bubble_sort(const int n, int A[static n]) {
  bool swapped = true;
  for (int i = 0; swapped && i < n - 1; ++i) {
    swapped = false;
    for (int j = n - 1; j > i; --j) {
      if (A[j] < A[j - 1]) {
	    swap(j, j - 1, A);
	    swapped = true;
      }
    }
  }
}

Loop Invariant

Consider loop invariant $P$ given by

A[0:i-1] is a sorted array of the i least elements of A.

We prove $P$ maintains the requisite properties:

• Initialization
  • When i = 0, A[0:-1] is an empty array. This trivially satisfies $P$.
• Maintenance
  • Suppose $P$ holds for some 0 ≤ i < n - 1. Then A[0:i-1] is a sorted array of the i least elements of A. Our inner loop now starts at the end of the array and swaps each adjacent pair, putting the smaller of the two closer to position i. Repeating this process across all pairs from n - 1 to i + 1 ensures A[i] is the smallest element of A[i:n-1]. Therefore A[0:i] is a sorted array of the i + 1 least elements of A. At the end of the iteration, i is incremented meaning A[0:i-1] still satisfies $P$.
• Termination
  • Termination happens when i = n - 1. Then $P$ implies A[0:n-2] is a sorted array of the n - 1 least elements of A. But then A[n-1] must be the greatest element of A meaning A[0:n-1], the entire array, is in sorted order.

Bibliography

• Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).