# How to sort fractions (small numbers)

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

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)
``````
• You forgot to subtract the q from the exponent. Jul 13, 2015 at 17:56
• Ok, you are right. But what about correctness and what about your ideas ? Jul 13, 2015 at 18:20
• You don't need to bring results from t to a if you make t have two fields where the second field is the subscript of the corresponding a. Jul 13, 2015 at 20:09
• What is your data type (or can that be defined)? Language restrictions? Can you use a built in sort? Why doesn't just defining the type and comparable and then tossing that into sort work?
– user40980
Jul 13, 2015 at 23:34

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)
``````
• Ok, I understand your point of view, but it is difficult to believe that we can't solve it faster (without comparison sort). Jul 14, 2015 at 20:38
• How much faster do you want to solve it? What are your requirements? Jul 14, 2015 at 20:46
• Your solution is too trivial for this problem. This task come from book, so is too simple what you proposed. Jul 15, 2015 at 14:58
• One day you may come to appreciate trivial solutions. Jul 15, 2015 at 16:24
• Ok, but it is too trivial Jul 15, 2015 at 16:26