Skip to content

Big O Visualizer

Quick Sort

Quicksort is a divide-and-conquer sorting algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. This can be done in-place, requiring small additional amounts of memory to perform the sorting.

Complexity

Quick Sort has a linearithmic best and average-case time complexity, which can be tested using a random list of numbers.

Quick Sort has a quadratic worst-case time complexity, which can be tested using a sorted (yes, that's right) list of numbers.

Fortunately, because Quick Sort performs so well on randomly sorted lists, the previous case can be easily mitigated by randomizing the input before executing the actual algorithm. Another solution is to change the pivot selection algorithm. Modern versions of Quick Sort use intelligent pivot selection algorithms in order to avoid the worst-case scenario in common data sets (e.g. sorted; reversed). However, even with these improved algorithms, it's always possible to construct an input that will produce worst-case performance.

Algorithm

Below the implementation of Quick Sort as used on this page.

src/algorithms/quick-sort.ts
1export default class QuickSort extends Algorithm {
2 name = "Quick Sort"
3 timeComplexityBest = Complexities.linearithmic
4 timeComplexityAverage = Complexities.linearithmic
5 timeComplexityWorst = Complexities.quadratic
6
7 execute(array: number[]): void {
8 this.quickSort(array)
9 }
10
11 swap(array: number[], i: number, j: number): void {
12 const tmp = array[i]
13 array[i] = array[j]
14 array[j] = tmp
15 }
16
17 partition(array: number[], left: number, right: number): number {
18 let q = left
19 let i
20 for (i = left; i < right; i++) {
21 if (array[i] < array[right]) {
22 this.swap(array, i, q)
23 q++
24 }
25 this.incrementOpCounter()
26 }
27 this.swap(array, i, q)
28 return q
29 }
30
31 quickSort(array: number[], left = 0, right: number = array.length - 1): number[] {
32 this.incrementOpCounter()
33 if (left < right) {
34 const pivot = this.partition(array, left, right)
35 this.quickSort(array, left, pivot - 1)
36 this.quickSort(array, pivot + 1, right)
37 }
38 return array
39 }
40}