Understanding the Netherlands National Flag Program

Question

I read the Dutch national flag , but could not understand that the arguments low and high are in threeWayPartition in the C ++ implementation.

If I assume that they will be sorted as the minimum and maximum elements of the array, then the if and else if do not make any sense, since (data[i] < low) and (data[i] > high) always return zero.

Where am I mistaken?

Answer 1

low and high are the values ​​that you defined for the trilateral partition, i.e. for a tripartite section, you only need two values:

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

In a C ++ program, what you move is the position in which the sections occurred. 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 tells you:

• Move the element above the bottom (i.e. p + 1 ), because everything below the bottom is already checked or
• Move the element below the top (i.e. q - 1 ), because everything above the vertex has already been checked or
• Leave the element in which it is located because it belongs to the middle.

You get [3, 1, 0, 2] , [6, 4] and [9, 8, 9] as the lower, middle, and upper sections, respectively.

Answer 2

} else if (data[i] >= high) { indicates that what you saw may not have been what was written in this article.

Answer 3

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