Sorting
Comparison and non-comparison based sorting — from bubble sort intuition to quicksort partitioning.
- 1 Lesson
Dry-run engine
Lomuto Partition
Quicksort's real work happens in place: one scan, a handful of swaps, zero extra arrays.
- Input
- arr = [7, 2, 9, 4, 3, 8, 5], pivot = arr[6] = 5
- Output · Partitioned
- Press play to run it
How it works
Scan j from left to right. When arr[j] <= pivot, increment i and swap arr[i] with arr[j]. Finally swap the pivot into arr[i + 1].
contiguous_ram_buffer[7]
- i-1
- j—
- Pivot5 @ idx 6
- Swaps0
Lomuto partition takes the last element, 5, as the pivot. i marks the end of the "≤ pivot" zone — -1 means the zone is empty — and j will scan every other cell once.
1 / 8
Course Contents
Related courses
- ArraysContiguous, indexable memory — the foundation almost every other data structure builds on.12 lessons · 16 problems
- StringsCharacter arrays with their own set of classic patterns — two pointers, sliding window, and more.19 lessons · 19 problems
- Linked ListNodes linked one direction by pointers instead of contiguous memory.4 lessons · 12 problems