AlgoScope

Dutch National Flag

Three pointers sort the array into less, equal and greater in one pass.

Array algorithms and techniques, algorithm, intermediate
Value 2 at mid. 2 is larger than 1, so it swaps up to index 7. High moves down, but mid stays: the value that came back is still unknown.active 0-61001221314052627lowmidhigh2 > 1
Value 2 at mid. 2 is larger than 1, so it swaps up to index 7. High moves down, but mid stays: the value that came back is still unknown.active 0-61001221314052627lowmidhigh2 > 1

Rotate, Partition, Select: Sort into less, equal, greater

Decision, step 2 of 10

2 is larger than 1, so it swaps up to index 7. High moves down, but mid stays: the value that came back is still unknown.

How rotate, partition, select works

Cost

Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(1)

Leads to

Topics that need this one first.

Taught by the same lesson

Rotate, Partition, Select covers these too, in the same run.