Quicksort

Updated: 25 March 2024

Quicksort

One of the two classical sorting algorithms, the other is MergeSort

Quicksort is regarded as one of the most import algorithms and is used as the base sort for many different programming languages

Algorithm

• Shuffle the array - important to guarantee performance
• Partition the array for some j
  • Entry a[j] is in place
  • No larger entry to the left of j
  • No larger entry to the right of j
• Sort each piece recursively

Partitioning

• Phase 1 - Repeat this until i and j cross each other
  • Scan i from left to right as long as a[i] < a[lo]
  • Scan j from right to left as long as a[j] > a[lo]
  • Exchange a[i] with a[j]
• Phase 2 - Pointers have crossed
  • Exchange a[lo] with a[j]
  • This is the final position of the partiion element

We can implement the partitioning logic as follows:

1
import { Comparison, type Compare } from './definition'
2
import { swap } from './swap'
3

4
export const partition = <T>(
5
  compare: Compare<T>,
6
  array: T[],
7
  lo: number,
8
  hi: number
9
) => {
10
  const lessThan = (a: T, b: T) => compare(a, b) === Comparison.Less
11

12
  let i = lo
13
  let j = hi + 1
14
  while (true) {
15
    while (lessThan(array[++i], array[lo])) if (i === hi) break
16

17
    while (lessThan(array[lo], array[--j])) if (j === lo) break
18

19
    if (i >= j) break
20

21
    swap(array, i, j)
22
  }
23

24
  swap(array, lo, j)
25
  return j
26
}

Sorting

The sort function makes use of the partitioning method above as described initially:

1
import type { Compare } from './definition'
2
import { partition } from './quicksort-partitioning'
3
import { shuffle } from './shuffle'
4

5
export const quickSort = <T>(compare: Compare<T>, array: T[]) => {
6
  const sort = (lo: number, hi: number) => {
7
    if (hi <= lo) return
8

9
    let k = partition(compare, array, lo, hi)
10

11
    sort(lo, k - 1)
12
    sort(k + 1, hi)
13
  }
14

15
  shuffle(array)
16
  sort(0, array.length - 1)
17
}

Details

• Partitioning in place. Can be done with a secondary array which makes partitioning easier but is not worth the cose
• Terminating the loop when pointers cros can be tricky
• Keeping our pointers in bounds and terminating the loop appropriately is important - The j==lo check is redundant in the snippet above but the i==hi one is required. This is because we will always find an element that is equal to the partitioning element since it is the element at the lo value
• Preserving randomness by shuffling is needed in order to guarantee performance
• Qhen duplicates are present it’s better to stop when we find a key equal to the partitioning item (duplicate)

Analysis

• A bit faster than merge sort
• Uses less memory than merge sort

In the worst case, quicksort is N^2 which is why we shuffle randomly

More specifically, the time compleixity of quicksort is 2(N+1) lg N. In the worst case quicksort can be N^2 - this is why we shuffle

Quicksort can be N^2 in some circumstances:

• Not randomized
• Lots of duplicates

Properties of Quicksort

• May have a large depth of recursion
• Not stable

Improvements:

• Using insertionsort when the subarrays are small
• Get a median sample using 3 random items to partition on

Selection

An application of quicksort

Given an array of N items, we want to find the kth largest item.

Things we know:

• Upper bound: We know we can solve it in N log N because we can just sort and then get the index we want
• Upper bound: kN since we can just look through till we get the element we want for k times
• Lower bound: N since we have to look at every item at least once

Can we define a selection algorithm that takes linear time (N)?

Algorithm

• Partition array so that
  • Entry a[j] is in place
  • No larger entry to the left of j
  • No entry smaller to the right of j
• Repeat in one subarray, depending on j, finished when j == k

1
import type { Compare } from './definition'
2
import { partition } from './quicksort-partitioning'
3
import { shuffle } from './shuffle'
4

5
/**
6
 * Get the `k`th element from an array (mutates the input `array`)
7
 */
8
export const quickSelect = <T>(compare: Compare<T>, array: T[], k: number) => {
9
  shuffle(array)
10

11
  let lo = 0
12
  let hi = array.length - 1
13

14
  while (hi > lo) {
15
    let j = partition(compare, array, lo, hi)
16

17
    if (j < k) lo = j + 1
18
    else if (j > k) hi = j - 1
19
    else return array[k]
20
  }
21

22
  return array[k]
23
}

On average, algorithm takes linear time N due to how we only ever recurse on one side, however there is the worst case which is N^2 but that is highly unlikely due to the shuffle

Duplicate keys

What happens to Quicksort when we have duplicated?

• Mergesort doesn’t really care about whether or not there are duplicate keys
• The quicksort implementation could take quadratic time if there were lots of duplicates depending on how the partitioning logic is implemented

3 Way Partitioning

If we accept that there may be duplicates, we can group all equal keys together which will give us a performance gain in the case of duplicate keys

Algorithm

• Let v be the partitioning item at a[lo]
• Scan i from left to right
  • a[i] < v - exchange a[lt] with a[i], increment lt and i
  • a[i] > v - exchange a[gt] with a[i], decrement gt
  • a[i] == v - increment i

Implementation

1
import { Comparison, type Compare } from './definition'
2
import { shuffle } from './shuffle'
3
import { swap } from './swap'
4

5
export const quickSort3Way = <T>(compare: Compare<T>, array: T[]) => {
6
  const sort = (lo: number, hi: number) => {
7
    if (hi <= lo) return
8

9
    let lt = lo
10
    let gt = hi
11
    let i = lo
12
    let v = array[lo]
13

14
    while (i <= gt) {
15
      let cmp = compare(array[i], v)
16

17
      if (cmp === Comparison.Less) swap(array, lt++, i++)
18
      else if (cmp === Comparison.Greater) swap(array, i, gt--)
19
      else i++
20
    }
21

22
    sort(lo, lt - 1)
23
    sort(gt + 1, hi)
24
  }
25

26
  shuffle(array)
27
  sort(0, array.length - 1)
28
}

This algorithm is N lg N when all are distinct and linear when there is only a constant number of distincy keys

Applications of Sorting

Sorting algorithms are used in many applications but can also be used to do things like:

• Find the median or duplicates
• Binary search
• Identify outliers
• Data compression
• Graphics
• Computational biology

Depending on our requirements we may need some specific sort atributes like:

• Stability
• Parallelization
• Determenistic
• Distinct/Duplicate keys
• Multiple key types
• Linked lists or arrays
• Large or small items
• Random vs partially sorted
• Performance guarantees