2
$\begingroup$

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.

Improve this question
$\endgroup$
4
$\begingroup$

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).

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ How can you implement those loops with only O(1) additional space? (A counter ranging over {0,1,2,3,...,n-2,n-1} would require ceil(log2(n)) bits of additional space.) $\endgroup$ – user12859 Apr 8 '15 at 3:30
  • 2
    $\begingroup$ @RickyDemer I believe you would assume memory addresses to be $O(1)$ space and then $n-1$ is simply the length of the array. $\endgroup$ – Pål GD Apr 8 '15 at 3:39
  • 6
    $\begingroup$ This is a standard algorithm known as counting sort. You should mention the name. $\endgroup$ – David Richerby Apr 8 '15 at 8:58
  • $\begingroup$ You have a redundant check in your else if line. $\;$ $\endgroup$ – user12859 Apr 8 '15 at 10:08
3
$\begingroup$

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).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.