14.4. Quick Sort#

The last sorting algorithm we discuss is quicksort. It is an efficient sorting algorithm that works on the principle of divide-and-conquer. The algorithm divides the array into two sub-arrays, and then recursively sorts (conquers) the sub-arrays. It is “quick” for large arrays compared to other sorting algorithms.

14.4.1. Algorithm#

The general idea of quicksort is based on the observation that if for an element in an array, all the elements to the left of it are smaller than it, and all the elements to the right of it are larger than it, then the element is in its correct position. We call this element the “pivot”. This is even if the elements on the right or left are not sorted. For example, in the following figure, 10 is a pivot.

pivot-example

The basic idea of quicksort is to pick a number and call it a pivot. This requires rearranging the array such that all elements on the left of the pivot are smaller than it, and all elements on the right of the pivot are larger than it. This is called the partitioning process.

The elements to the left of the pivot is considered a “left sub-array”, and the elements on the right are “right sub-array”. The partitioning process is then done recursively for the left and right sub-arrays. This happens until the sub-arrays are of size 1, which means they are sorted.

Given the following example array named int A[] = {9, 5, 18, 8, 5, 2};,

quick-sort-array-example

the algorithm works as follows:

  1. Pick a pivot element from the array that we will place in its correct position. We can pick the first element. Then, we can start from index left = 1 and right = 8. We will increment left++ until we find an element that is smaller than the pivot on A[left], and decrement right-- until we find an element at A[right] that is larger than the pivot. In the following example, left stops at 1 and right stops at 8.

    pick-pivot

  2. We then swap A[left] and A[right]. This brings the smaller element to the left and the larger element to the right.

    first-swap-partition

  3. We increment left till A[left] > pivot and decrement right till A[right] < pivot. In the following example, left stops at 3 and right stops at 7, and we swap A[left] and A[right].

    second-swap-partition

  4. We repeat this process and notice elements smaller than the pivot are populating the left and greater than pivot populating the right. left stops at 4 and right stops at 6, and we swap A[left] and A[right].

    third-swap-partition

  5. We continue this process until left surpasses right. Notice this happens when left is at the element that is greater than the pivot, and right should stop at the element that is smaller than the pivot. In the following example, left stops at 6 and right stops at 5.

    fourth-swap-partition

  6. When we get left > right, we swap A[right] with pivot. This places the pivot in its correct position.

    final-swap-partition

  7. We then recursively call quicksort, where we continue partitioning, on the left and right sub-arrays.

    quicksort-recursive

For example, if we do the partitioning on the right sub-array,

  • we start with pivot as element at index 6, left = 7 and right = 8.

    quicksort-right-subarray

  • we increment left till either A[left] > pivot or left > right. If left > right, we shouldn’t decrement right till A[right] < pivot. In the following example, left stops at 9 and right remains at 8.

    quicksort-right-subarray-left

  • we then have to swap A[right] and pivot. This places the pivot in its correct position.

    quicksort-right-subarray-swap

  • we then recursively call quicksort on the left and right sub-arrays, but there is no right sub-array, so we only call quicksort on the left sub-array.

    quicksort-right-subarray-recursive

14.4.2. Pseudocode#

We write divide the pseudocode for quicksort into two function. The first function is the partitioning function, which takes in the array, the left index, and the right index.

  1. Set pivotInd to left holding the index of the pivot element.

  2. Set left to left + 1 to start from the next element.

  3. Increment left till A[left] > pivot or left > right.

  4. Decrement right till A[right] < pivot or left > right.

  5. If left < right, swap A[left] and A[right].

  6. Otherwise, swap A[right] and A[pivotInd].

  7. Repeat steps 3-6 until left > right.

The second function is the quicksort function, which takes in the sub-array, with the low and high index, holding the left most index of the sub-array and the rightmost index of the sub-array, respectively.

  1. If low < high, call the partitioning function on the sub-array from index low to high, and there left will be set to low and right will be set to high.

  2. Partitioning function returns the index of the pivot element, which we will call pivotInd.

  3. Call quicksort on the left sub-array from low to pivotInd - 1.

  4. Call quicksort on the right sub-array from pivotInd + 1 to high.

14.4.3. Implementation#

The following code snippet shows the implementation of partition and quicksort sort functions. Download quicksort.c if you want to play with the code.

Code

 1#include <stdbool.h>
 2#include <stdio.h>
 3
 4void swap(int list[], int left, int right) {
 5  int t = list[right];
 6  list[right] = list[left];
 7  list[left] = t;
 8}
 9
10void printArray(int list[], int listLength) {
11  for (int i = 0; i < listLength; i++) {
12    printf("%d ", list[i]);
13  }
14  printf("\n");
15}
16
17int partition(int list[], int low, int high) {
18  int pivot = low, left = low + 1, right = high;
19  printf("left = %d, right = %d\n", left, right);
20  while (true) {
21    while (left <= right && list[left] <= list[pivot]) {
22      left++;
23    }
24
25    while (left <= right && list[right] > list[pivot]) {
26      right--;
27    }
28
29    if (left < right) {
30      swap(list, left, right);
31    } else {
32      swap(list, pivot, right);
33      return right;
34    }
35  }
36}
37
38void quicksortHelper(int list[], int low, int high) {
39  if (low < high) {
40    int pivot = partition(list, low, high);
41
42    printArray(list, 9);
43
44    quicksortHelper(list, low, pivot - 1);
45    quicksortHelper(list, pivot + 1, high);
46  }
47}
48
49void quicksort(int list[], int length) {     
50    quicksortHelper(list, 0, length - 1); 
51}
52
53int main(void) {
54  int list[9] = {10, 14, 8, 13, 20, 3, 6, 9, 4};
55
56  quicksort(list, 9);
57  printArray(list, 9);
58  return 0;
59}

Output

left = 1, right = 8
3 4 8 9 6 10 20 13 14 
left = 1, right = 4
3 4 8 9 6 10 20 13 14 
left = 2, right = 4
3 4 8 9 6 10 20 13 14 
left = 3, right = 4
3 4 6 8 9 10 20 13 14 
left = 7, right = 8
3 4 6 8 9 10 14 13 20 
left = 7, right = 7
3 4 6 8 9 10 13 14 20 
3 4 6 8 9 10 13 14 20

In-progress!