Understanding Dutch National flag Program

Question

I was reading the Dutch national flag problem, but couldn't understand what the `low` and `high` arguments are in the `threeWayPartition` function in the C++ implementation. If I assume them as min and max elements of the array to be sorted, then the `if` and `else if` statements doesn't makes any sense since `(data[i] < low)` and `(data[i] > high)` always returns zero. Where am I wrong?

Accepted Answer

`low` and `high` are the values you have defined to do the three-way partition i.e. to do a three-way partition you only need two values:

```
[bottom] <= low  < [middle] < high <= [top]
```

In the C++ program what you are moving are the positions where the partitions occurred. A step-by-step example:

```
data = [ 3, 1, 4, 9, 8, 2, 6, 9, 0 ]
low  = 4
high = 8
```

```
   [ 3 , 1 , 4 , 9 , 8 , 2 , 6 , 9 , 0 ]
p^  i^                                  q^
```

```
   [ 3 , 1 , 4 , 9 , 8 , 2 , 6 , 9 , 0 ]
    p^  i^                              q^
```

```
   [ 3 , 1 , 4 , 9 , 8 , 2 , 6 , 9 , 0 ]
        p^  i^                          q^
```

```
   [ 3 , 1 , 4 , 9 , 8 , 2 , 6 , 9 , 0 ]
        p^      i^                      q^
```

```
   [ 3 , 1 , 4 , 0 , 8 , 2 , 6 , 9 , 9 ]
        p^      i^                  q^
```

```
   [ 3 , 1 , 0 , 4 , 8 , 2 , 6 , 9 , 9 ]
            p^      i^              q^
```

```
   [ 3 , 1 , 0 , 4 , 9 , 2 , 6 , 8 , 9 ]
            p^      i^          q^
```

```
   [ 3 , 1 , 0 , 4 , 6 , 2 , 9 , 8 , 9 ]
            p^      i^      q^
```

```
   [ 3 , 1 , 0 , 4 , 6 , 2 , 9 , 8 , 9 ]
            p^          i^  q^
```

```
   [ 3 , 1 , 0 , 2 , 6 , 4 , 9 , 8 , 9 ]
                p^         iq^
```

As the algorithm says you:

- Swap the element above the bottom (i.e. `p + 1`) because everything below the bottom has been already checked, or

- Swap the element below the top (i.e. `q - 1`) because everything above the top has been already checked, or

- Leave the element where it is because it belongs to middle.

You get `[3, 1, 0, 2]`, `[6, 4]` and `[9, 8, 9]` as bottom, middle and top partitions respectively.

Understanding Dutch National flag Program

Solution

Problem