We have $10^5$ fractions: $\frac{p}{2^q}$ such that $0 \leq p,q \leq 10$.
Find (fast) algorithm which sorts them.

I ask you to look at my proposition and tell me your ideas. $\frac{p}{q}$ is represented as the ordered pair $(p, q)$.

On input we have an array a.

My idea:

for i = 1 to n 
do t[i] = a[i].first * 2^(10)
countsort (t)
bring results from t to a (remember about / 2^10)

II Idea:

for i = 1 to n do       
   t[i] = a[i].first * 2^(10)
{ now we have only integer numbers }
sort t by counting (as bucket use bits)
for i = 1 to n do
   a[i] = t/2^10

In this way we have O(n + log (10 * 1024)n) = O(14n).
What about this solution ?

  • 3
    $\begingroup$ I'm confused. Why can you not use any regular sorting algorithm (with a tailored comparison function)? $\endgroup$ – Raphael Jul 23 '15 at 14:20
  • 1
    $\begingroup$ I cannot understand your pseudocode at all. Mind explaining it a little more clearly? @user220688 $\endgroup$ – Sagnik Jul 23 '15 at 18:38
  • 1
    $\begingroup$ @Raphael Using counting sort is faster. There are less than $121$ possible fractions. $\endgroup$ – Yuval Filmus Jul 23 '15 at 19:05
  • 1
    $\begingroup$ Seems tailor-made for counting sort. So I don't understand what the poster is confused about. $\endgroup$ – Kyle Jones Jul 23 '15 at 19:35
  • 1
    $\begingroup$ What's your question? "Tell me your ideas" is not a question. This site is for specific, focused questions that admit a single answer. How will you evaluate answers? $\endgroup$ – D.W. Jul 23 '15 at 21:26

You can sort all $11^2$ possible fractions, and create a table mapping $p/2^q$ to its position in this ordering, and another table going the other way. Then you can use counting sort to handle $N$ fractions in time $O(11^2 + N)$. (Here the underlying constant is universal, not depending on the size of the domain.)

  • $\begingroup$ Sorry, why $O(11^2 N)$? I think it should be $O(N)$ for putting every number in bucket and then $O(11^2 + N)$ for forming resulting array. I know that $O(11^2 N) = O(2N + 11^2)$ , just $O(11^2 N)$ is little confusing. $\endgroup$ – knok16 Jul 23 '15 at 21:14
  • $\begingroup$ I edited my first post, could you look at it ? $\endgroup$ – user220688 Jul 26 '15 at 16:36
  • $\begingroup$ Probably worth saying "counting sort" here. $\endgroup$ – David Richerby Jul 26 '15 at 16:47

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