I'm reading the Dutch national flag problem and I don't get it: why is this different from a simple sorting problem?
I mean: if we assign 0 to the red color, 1 to white and 2 to blue and do a standard quicksort or whatever.. why should I not get the right answer?
Am I missing something?
The Dutch National Flag Problem is just a special case of the more general sorting problem where the only permissible elements are 0, 1, and 2. You can absolutely solve it using a standard sorting algorithm.
The problem is interesting in of itself partially for historical reasons but largely because it's challenging to find solutions that are stable, time-efficient (O(n)), and space-efficient (O(1)). It's easy to get solutions with two of these three properties, but getting all three is (I believe) an open problem. It's also interesting as a venue for developing algorithms for quick sort and partitioning with duplicate keys; you can think of 0, 1, and 2 as less than the pivot, equal to the pivot, and greater than the pivot and you basically have quick sort with repeated elements.
Hope this helps!