How to sort fractions (small numbers)

Question

We have 100 000 fractions: Let's consider following fractions. p/(2^q) such that 0 <= p,q <= 10

As you can see there are <= 10 * 10 different fractions, but we have 100 000 that we have to sort them (so there are little unique elements).

Task is about thinking fast algorithm to sort fractions.

I ask you for looking at my proposition and show me your ideas. (I assume that fractions are given by pair, for instance: p/q <----> (p, q) ) on input we have 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)

Answer 1

First, your definition of your numbers can lead to non-fractions (e.g., p=2, q=0).

Second, to summarize your idea:

1. Store all your fractions as integers
2. Perform an integer sort
3. Convert all your integers back to fractions

Seems like a lot of unnecessary memory and time when a lot of sorting algorithms can be done using a simple comparison sort and you can leave your data in its original form.

With a comparison sort, you only have to implement a custom comparison operator that exploits knowledge of your specialized fractions. For example in C++, you could use the built-in sort function and just implement your own comparator.

The comparator function compare(a,b) just needs to return true if fraction a is less then fraction b otherwise return false. For example, this function can exploit the fact that multiplying by 2 can be done as a bit shift. So your comparison could look something like

a.first * (1 << b.second) < b.first * (1 << a.second)