CODEWITHSUNDEEP
algorithmpartitioning
abhi120
abhi120

Reputation: 278

Understanding Dutch National flag Program

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?

Upvotes: 4

Views: 9674

Answers (3)

Alexander
Alexander

Reputation: 23537

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.

Upvotes: 9

Blastfurnace
Blastfurnace

Reputation: 18652

Think of low and high as the half-open range [low,high) for values in the middle partition. All values less than low end up in the left partition. The middle partition will contain the values from low up to, but not including, high. Finally, all values greater than or equal to high end up in the right partition.

Upvotes: 0

bluevector
bluevector

Reputation: 3493

} else if (data[i] >= high) { shows that what you though you saw might not be what was written in the article.

Upvotes: 1

Related Questions