An array A holds n integers, and all integers in A belong to the set {0,1,2}. Describe an O(n) sorting algorithm for putting A in sorted order. Your algorithm may not make use of auxiliary storage such as arrays or hash tables. More precisely, the only additional space used, beyond the given array is O(1). Give an argument to explain why your algorithm runs in O(n) time.
This is a self-answered question, but other answers are certainly desired.
My answer was the following:
Algorithm Sort(A, n)
Input: an array A of n integers, the element of A belong to the set {0,1,2}
Output: A is sorted
int zero ← 0, one ← 0
for i = 0 to n-1
// we count the number of occurrences of each element in the array
switch(A[i])
case 0:
zero ← zero + 1
case 1:
one ← one + 1
// 2 would be be n - ( zero + one)
// now we populate the array
for i = 0 to n – 1{
if i < zero then A[i] = 0
else if i < zero + 1 then A[i] = 1
else A[i] = 2
The algorithm traverses the array twice, so its execution time is at least 2n. I was thinking of a way to get rid of the second for loop, but I doubt it can be avoided, unless the input array is already sorted or it contains element of the same type. In any case 2n is O(n).
else if line. $\;$
$\endgroup$
– user12859
Apr 8 '15 at 10:08
This is the Dutch National Flag Problem. It has been examined in depth due to its use in Quicksort, and methods are given in the literature about that algorithm. Sedgewick gives a method in his paper on Multikey Quicksort due to the need for ternary partitioning in radix-based sort.
James R. Bitner, “An Asymptotically Optimal Algorithm for the Dutch National Flag Problem,” SIAM J. Comput., 11(2), 243–262 found lower bounds on swaps and how to get arbitrarily close to them (i.e. how to tune the constant on O(n) as a function of working space).
