Sorting algorithm which does not allow counting of elements

Question

I have seen acrosss in a company interview test this question, but i am not clear about the question first. Could you people clarify my doubt ?

Question : Write a program to sort an integer array which contains Only 0's,1's and 2's. Counting of elements not allowed, you are expected to do it in O(n) time complexity.

Ex Array : {2, 0, 1, 2, 1, 2, 1, 0, 2, 0}

Answer 1

Output to a linked list.

• Remember the beginning of the list.
• Remember the position where the 1s start.
• Remember the end of the list.

Run through the whole array.

• If you encounter a 0, add it to the first position of the linked list.
• If you encounter a 1, add it after the position of the 1.
• If you encounter a 2, add it at the end of the list.

HTH

Raku

Answer 2

Instead of blasting you with yet another unintelligible pseudo-code, I’ll give you the name of the problem: this problem is known as the Dutch national flag problem (first proposed by Edsgar Dijkstra) and can be solved by a three-ways merge (see the PHP code in the first answer which solves this, albeit very inefficiently).

A more efficient in-place solution of the threeways merge is described in Bentley’s and McIlroy’s seminal paper Engineering a Sort Function. It uses four indices to delimit the ranges of the intermediate array, which has the unsorted values in the middle, the 1s at both edges, and the 0s and 2s in-between:

After having established this invariant, the = parts (i.e. the 1s) are swapped back into the middle.