Dutch National Flag
Three pointers sort the array into less, equal and greater in one pass.
Rotate, Partition, Select: Sort into less, equal, greater
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.
Cost
- Best
- O(n)
- Average
- O(n)
- Worst
- O(n)
- Space
- O(1)
Before this
Leads to
Topics that need this one first.
Taught by the same lesson
Rotate, Partition, Select covers these too, in the same run.