sreejithmvarma.in

PCCST303 · Module 4: Sorting and Searching

Quick Sort

Selection and insertion sort both work through the array one position at a time, O(n²) in general. Quick sort takes a completely different approach: split the problem in half (roughly) using a pivot, and recurse.

Idea

Definition

Quick sort picks a pivot element and partitions the array so every element smaller than the pivot ends up to its left, and every element larger ends up to its right. The pivot is now in its final sorted position. The two sides are then sorted recursively, independently of each other.

This is divide and conquer: partitioning does the "divide" step, and the two recursive calls do the "conquer."

Partitioning

The core operation. Using the last element as pivot (a common, simple choice):

PARTITION(A, LOW, HIGH)
// A is the array being sorted
// LOW is the starting index of the segment to partition
// HIGH is the ending index of the segment to partition
 
1. PIVOT = A[HIGH]
2. i = LOW - 1
3. For j = LOW to HIGH - 1:
       If A[j] <= PIVOT:
           i = i + 1
           Swap A[i] and A[j]
4. Swap A[i+1] and A[HIGH]
5. Return i + 1        (the pivot's final index)

Key Idea

i tracks the boundary of "elements confirmed smaller than the pivot so far." Every time A[j] <= PIVOT is found, that element is swapped into the next slot just past that boundary, growing the smaller-than-pivot region by one. Elements greater than the pivot are simply skipped over, left in place until the final pivot swap.

Worked partition example

Partitioning [8, 3, 7, 4, 9, 2, 6] with pivot = A[6] = 6. Initially i = -1 (no elements confirmed smaller yet, off the left edge) and j = 0:

Index
8
3
7
4
9
2
6
0123456
↑j

j=0: A[0]=8 > 6, skip. j=1: A[1]=3 <= 6, i becomes 0, swap A[0] and A[1]:

Index
3
8
7
4
9
2
6
0123456
↑i
↑j

j=2: A[2]=7 > 6, skip. j=3: A[3]=4 <= 6, i becomes 1, swap A[1] and A[3]:

Index
3
4
7
8
9
2
6
0123456
↑i
↑j

j=4: A[4]=9 > 6, skip. j=5: A[5]=2 <= 6, i becomes 2, swap A[2] and A[5]:

Index
3
4
2
8
9
7
6
0123456
↑i
↑j

Loop ends (j reaches HIGH). Final swap: A[i+1] and A[HIGH], i.e. A[3] and A[6]:

Index
3
4
2
6
9
7
8
0123456

6 is now at index 3, its correct sorted position: everything left (3, 4, 2) is smaller, everything right (9, 7, 8) is larger.

Full algorithm

QUICK_SORT(A, LOW, HIGH)
// A is the array to sort
// LOW is the starting index of the segment to sort
// HIGH is the ending index of the segment to sort
 
1. If LOW < HIGH:
       PIVOT_INDEX = PARTITION(A, LOW, HIGH)
       QUICK_SORT(A, LOW, PIVOT_INDEX - 1)
       QUICK_SORT(A, PIVOT_INDEX + 1, HIGH)
2. Stop.

Continuing from the partition above, 6 (index 3) is fixed. The two sides, [3, 4, 2] (indices 0..2) and [9, 7, 8] (indices 4..6), are now sorted independently by recursive calls, each partitioning again around its own last element:

Index
3
4
2
6
9
7
8
0123456

Left side, QUICK_SORT(A, 0, 2). Partition [3, 4, 2] with pivot A[2] = 2: A[0] = 3 > 2 and A[1] = 4 > 2, both skipped, so i never advances. Final swap A[0] and A[2], placing 2 at index 0:

Index
2
4
3
6
9
7
8
0123456

The left partition (indices 0..-1) is empty, done. The right partition, QUICK_SORT(A, 1, 2) on [4, 3], partitions with pivot A[2] = 3: A[1] = 4 > 3, skipped. Final swap A[1] and A[2], placing 3 at index 1:

Index
2
3
4
6
9
7
8
0123456

Right side, QUICK_SORT(A, 4, 6). Partition [9, 7, 8] with pivot A[6] = 8: A[4] = 9 > 8, skipped. A[5] = 7 <= 8, so i becomes 4, swap A[4] and A[5]:

Index
2
3
4
6
7
9
8
0123456

Final swap A[5] and A[6], placing 8 at index 5:

Index
2
3
4
6
7
8
9
0123456

Both remaining partitions are single elements, already sorted. The array is now fully sorted: [2, 3, 4, 6, 7, 8, 9].

Choosing a pivot

The pivot choice matters a lot. A pivot that splits the array roughly in half each time gives O(n log n). A pivot that's always the smallest or largest remaining element (e.g. always picking the last element on an already-sorted array) gives one side of size 0 and the other of size n-1 every time, degrading to O(n²). This is why some implementations pick the pivot randomly, or use "median of three" (median of first, middle, last), to make the worst case unlikely.

Complexity

CaseComplexity
Best (balanced partitions)O(n log n)
AverageO(n log n)
Worst (always unbalanced)O(n²)
SpaceO(log n) average, from the recursion stack
StabilityNot stable, partitioning can reorder equal elements

Quick recall

  • Partition around a pivot: smaller elements left, larger elements right, pivot lands in its final position.
  • Recursively quick-sort each side independently, the classic divide-and-conquer pattern.
  • i tracks the boundary of the "confirmed smaller" region during partitioning; every qualifying element gets swapped just past it.
  • Average/best case O(n log n); worst case O(n²) when partitions are consistently unbalanced (e.g. sorted input with last-element pivot).
  • In-place with O(log n) recursion-stack space; not stable.