This problem is a variant of the quick sort algorithm
, so we know we'll need to do some form of partitioning. Partitioning
is the act of splitting an array up into sub-arrays, "according to whether they are less than or greater than" a pivot number.
At first glance, it seems like an impossible task: how can we determine where an element should go without being aware of its relative positioning compared with the rest of the elements?
There's one way-- by using multiple pointers.
The idea behind the final dutch national flag algorithm is to use three pointers, low
, mid
, and high
. We start with low
and mid
initialized to 0
, and our goal is to expand these "groups" (the sub-array from one of these indices to the next) over time. We'll do this via a series of swaps.
Don't worry, we'll break this down more as we go.
