CODEWITHSUNDEEP
algorithmsortinglanguage-agnostic
Dean
Dean

Reputation: 6958

Difference between Dutch National Flag problem and sorting

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?

Upvotes: 2

Views: 1039

Answers (2)

templatetypedef
templatetypedef

Reputation: 373082

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!

Upvotes: 1

gen-y-s
gen-y-s

Reputation: 881

In this problem the range of values of items to be sorted is small. In such cases it's possible to use non-comparison sort (eg, such as counting sort) to sort the array. Non comparison sort algorithms can sort in O(n) that is, faster than regular comparison sort algorithms such as quicksort.

Upvotes: 0

Related Questions