C in 100 Seconds: Quick Sort

Quick Sort — Partition, Pivot, In-Place

Pick a pivot, partition the array so everything smaller is on the left and everything larger is on the right, then recursively sort both sides. No extra array needed.

The Partition

int partition(int arr[], int low, int high) {
  int pivot = arr[high];
  int i = low - 1;
  for (int j = low; j < high; j++) {
    if (arr[j] < pivot) {
      i++;
      swap(&arr[i], &arr[j]);
    }
  }
  swap(&arr[i + 1], &arr[high]);
  return i + 1;
}

Walk through the array. Anything smaller than the pivot gets swapped to the front. After the loop, put the pivot in its final position.

The Recursive Sort

void quick_sort(int arr[], int low, int high) {
  if (low < high) {
    int pi = partition(arr, low, high);
    quick_sort(arr, low, pi - 1);
    quick_sort(arr, pi + 1, high);
  }
}

Output

Before: 10 80 30 90 40 50 70
After:  10 30 40 50 70 80 90

Average O(n log n), in-place, and usually faster than merge sort in practice.

Student code: GitHub