5.1 - The Dutch National Flag Problem - Variants (Reorder together)

#1

Hi EPI,

For the variants to The Dutch National Flag Problem that deal with reordering the array so that all objects with the same key appear together (variants 1 and 2), do we assume that we know what the distinct keys are?

If I know what the 3 or 4 distinct values are, I think I could modify the optimal flag solution by partioning around the distinct keys instead of “smaller”, “equal”, “larger”.

On the other hand, if we are only given a single index to partition around, I am not sure of I can come up with a solution that doesn’t first identify the distinct keys.

Please let me know if my reasoning makes sense or if you need me to clarify.

Best,

Kola

0 Likes
#2

For variants 1 and 2, you do know the values of keys but they might not have any relation (i.e., total ordering). Let me know if you have any other problem.

0 Likes