Let A be an array A[0..n-1].

The array has n items.

Each item is labeled with one of these letters: {R,V,B}.

For example, A[0].label=V, A[1].label=R, etc.

What is the best algorithm for sorting items of A in lexicographic order? What is its time complexity?

I don't know if I could apply counting sort, because each element is in a range [0..k] with k=2, supposing that we can give an integer value to each letter (B=0, R=1, V=2).

  • $\begingroup$ Use counting sort. $\endgroup$ – Yuval Filmus May 10 '18 at 22:02
  • $\begingroup$ @YuvalFilmus so is my intuition correct? If yes, I assume that cost d*(n+k), where d=tuple dimension, should be 1*(n+2)=O(n) in this case. $\endgroup$ – Marco R. May 10 '18 at 22:09

Your Answer

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

Browse other questions tagged or ask your own question.