QuickSort Algorithm

4 min readSep 19, 2022

A in-place sorting algorithm that picks a “pivot” element from an array and partition the rest of the elements into two subarrays. Elements less than the pivot are move to the left subarray and elements greater than the pivot are move to the right subarray. The algorithm sorts those subarrays recursively. On average, quicksort runs in O(nlog(n)) time. In worst case, it is O(n²) time when unluckily keep choosing the smallest or the greatest element as a pivot.

Table of Contents· How Does QuickSort Algorithm Work?
  ∘ 1. Pick a pivot from the array
  ∘ 2. Rearrange the array
  ∘ 3. Partition
· Graphical Explanation
· Code Implementation
  ∘ Complexity
  ∘ Pseudocode
  ∘ Golang
  ∘ Python

How Does QuickSort Algorithm Work?

Recursively pick, rearrange, and partition.

1. Pick a pivot from the array

There are many different ways to choose a pivot from the given array.

the first element(implemented here)
the last element
a random element
median

2. Rearrange the array

move elements less than the pivot to the left side(not in sorted order yet)
move elements greater than the pivot to the right side(not in sorted order yet)
put the pivot at its correct position in a sorted array

3. Partition

Divide the array into two smaller subarrays, left(elements less than pivot)and right subarray(elements larger than pivot). Recursively sort each subarray until it contains a single element(base case).

For each pass, only the pivot is at its final position in the sorted array. The left and right subarrays are continuous to be sorted recursively and respectively.

Graphical Explanation

step1: Pick a pivot. (We choose the first element as a pivot to implement here.)
step2: Rearrange the array

step3: Partition
Divide the array to left and right subarray based on the pivot
step4: Recursively implement step1 to step3 until all the subarrays have only one element left.

Code Implementation

Complexity

Time: Best O(nlog(n)), Average O(nlog(n)), Worst O(n²)
The worst case occurs when the greatest or smallest element is always picked as a pivot.
Space: O(n) for recursive call stacks
n: the total number of elements in the input array

Pseudocode

# base case
if startIdx >= endIdx:
   return# pick the first element as a pivot
pivotIdx = startIdx
leftIdx = startIdx + 1
rightIdx = endIdx# rearrange the array
while leftIdx <= rightIdx:
    if array[leftIdx] > array[pivotIdx] and array[rightIdx] < array[pivotIdx]:
        swap array[leftIdx] and array[rightIdx]
    if array[leftIdx] <= array[pivotIdx]:
        leftIdx += 1
    if array[rightIdx] >= array[pivotIdx]:
        rightIdx -= 1swap array[pivotIdx] and array[rightIdx]# partition
quickSort(left subarray)
quickSort(right subarray)

Golang

Python

You can access the source code here.

Other sorting algorithms: