6.1 The Dutch National Flag Problem


The book says,

One solution is to reorder the array so that all elements less than the pivot appear first, followed by elements equal to the pivot, followed by elements greater than the pivot.

Generalizing, suppose A = 〈0,1,2,0,2,1,1〉, and the pivot index is 3. ThenA[3] = 0, so 〈0,0,1,2,2,1,1〉 is a valid partitioning. For the same array, if the pivot index is 2, then A[2] = 2, so the arrays 〈0,1,0,1,1,2,2〉 as well as 〈0,0,1,1,1,2,2〉 are valid partitionings.

How come 〈0,1,0,1,1,2,2〉 is a valid partition for index 2 and 〈0,0,1,2,2,1,1〉 is a valid partition for index 3?
As it violates the rule in the first statement.