Pattern Recognition Drill

#31 — Quick sort (Lomuto partition)

Medium Sorting

The Problem

Sort an array using quicksort with Lomuto partition.

What approach would you use?

Think about it before scrolling down.

Key Signals

Partition: pick pivot, rearrange so elements < pivot are left, > pivot are right
Pivot is in its final position after partition

Divide & Conquer

Partition places pivot correctly. Recurse on left and right partitions. O(n log n) average.

Common Trap

Worst case is O(n²) with bad pivot choice (already sorted). Random pivot selection avoids this.

← #30 #32 →