Quick sort

2018-04-23

Content:

1. The idea

Say we want to sort an array in ascending order.

The quick sort algorithm’s idea is that you choose a random element in the array, let’s call it pivot, then you reorder the array so that it has the form elements < pivot, pivot, elements > pivot, then do the same thing for those 2 unsorted parts.

Figure 1. Quick sort visualization
(Source: Wikipedia - Quick sort)

2. Implementation

N = length of array.

Say we want to quick sort an array from index left to right. Like I mentioned, first you need to choose a pivot value and reorder the array, the reordering phase is called partition.

Theorically, you can choose whatever pivot value you want, since I find the Lomuto partition scheme intuitive, I’m gonna pick the last element as the pivot:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

void quick_sort(vector<int>& arr) {
  int n = arr.size();
  quick_sort(arr, 0, n-1);
}

// overload
void quick_sort(vector<int>& arr, int left, int right) {
  // int pivotIndex = right;
  int correctPivotIndex = partition(arr, left, right);
}

int partition(vector<int>& arr, int left, int right) {
  int i = left;
  for(int j = left; j < right; j++)
    if (arr[j] <= arr[right])
      swap(arr[i++], arr[j]);
  swap(arr[i], arr[right]);
  return i;
}

void partition

Some notice here:

  • The chosen pivot value is arr[pivotIndex].
  • After partition: arr[left..correctPivotIndex] <= pivot value and arr[correctPivotIndex+1..right] > pivot value.
  • The pivot value is now placed at its correct position in the sorted array (i.e. at correctPivotIndex-th index).

Now we need to sort the 2 unsorted part recursively (and also add the base case):

1
2
3
4
5
6
7
8
9

// overload
void quick_sort(vector<int>& arr, int left, int right) {
  if (left >= right) return;
  
  // int pivotIndex = right;
  int correctPivotIndex = partition(arr, left, right);
  quick_sort(arr, left, correctPivotIndex-1);
  quick_sort(arr, correctPivotIndex+1, right);
}

It’s late I need to go home..