DAA 15a_partition Divide & Conquer

Partition (Lomuto Scheme) — Visualizer

Partition is the 핵심 (core) building block of Quick Sort. Using Lomuto (textbook), we keep the pivot at r, scan with j, and maintain a “≤ pivot” region using i (boundary index).

➡ Quick Sort

Visualizer

Step: 0 / 0

Array (comma-separated)

Auto-play speed (ms)

Smaller ms = faster (e.g., 120 fast, 1000 slow).

l (left index)

Start of subarray to partition.

r (right index)

Pivot will be A[r].

Pivot choice

Helps connect to Randomised Quick Sort.

Dim outside active range Show pivot Show pointers (i, j)

Legend Active Range pivot i boundary j scanner

Ops: 0

l, r

—

pivot (idx:value)

—

i, j

—

comp / swaps

0 / 0

Explain

Enter array and choose l, r, then press Start. Partition will place the pivot into its final index k.

Loop Invariant (Textbook Lomuto)

Pseudocode (Lomuto Partition — Textbook)

Highlighted line matches the current step.

Goal: After partition, pivot ends at index k such that: A[l..k-1] ≤ pivot and A[k+1..r] > pivot.

Output

Pivot final index k: —

Run partition multiple times with different l, r to see how pivot is placed for that subarray.