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)
  • 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 ?
    – user220688
    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 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)
  • Ok, I understand your point of view, but it is difficult to believe that we can't solve it faster (without comparison sort).
    – user220688
    Jul 14, 2015 at 20:38
  • How much faster do you want to solve it? What are your requirements?
    – dpmcmlxxvi
    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.
    – user220688
    Jul 15, 2015 at 14:58
  • One day you may come to appreciate trivial solutions.
    – dpmcmlxxvi
    Jul 15, 2015 at 16:24
  • Ok, but it is too trivial
    – user220688
    Jul 15, 2015 at 16:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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