# How to sort $N$ fractions from finite set [closed]

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

• I'm confused. Why can you not use any regular sorting algorithm (with a tailored comparison function)? – Raphael Jul 23 '15 at 14:20
• I cannot understand your pseudocode at all. Mind explaining it a little more clearly? @user220688 – Sagnik Jul 23 '15 at 18:38
• @Raphael Using counting sort is faster. There are less than $121$ possible fractions. – Yuval Filmus Jul 23 '15 at 19:05
• Seems tailor-made for counting sort. So I don't understand what the poster is confused about. – Kyle Jones Jul 23 '15 at 19:35
• 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? – 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.)
• 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. – knok16 Jul 23 '15 at 21:14