# 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.

(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..*