# Quick Sort

## Contents

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

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};`

,

the algorithm works as follows:

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`

.We then swap

`A[left]`

and`A[right]`

. This brings the smaller element to the left and the larger element to the right.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]`

.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]`

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

.When we get

`left > right`

, we swap`A[right]`

with`pivot`

. This places the pivot in its correct position.We then recursively call quicksort, where we continue partitioning, on the left and right sub-arrays.

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`

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

.we then have to swap

`A[right]`

and`pivot`

. This places the pivot in its correct position.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.

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

Set

`pivotInd`

to`left`

holding the index of the pivot element.Set

`left`

to`left + 1`

to start from the next element.Increment

`left`

till`A[left] > pivot`

or`left > right`

.Decrement

`right`

till`A[right] < pivot`

or`left > right`

.If

`left < right`

, swap`A[left]`

and`A[right]`

.Otherwise, swap

`A[right]`

and`A[pivotInd]`

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

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`

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

`pivotInd`

.Call quicksort on the left sub-array from

`low`

to`pivotInd - 1`

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