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. – CodesInChaos Jul 13 '15 at 17:56
  • Ok, you are right. But what about correctness and what about your ideas ? – user220688 Jul 13 '15 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. – A. I. Breveleri Jul 13 '15 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 '15 at 23:34

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 '15 at 20:38
  • How much faster do you want to solve it? What are your requirements? – dpmcmlxxvi Jul 14 '15 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 '15 at 14:58
  • One day you may come to appreciate trivial solutions. – dpmcmlxxvi Jul 15 '15 at 16:24
  • Ok, but it is too trivial – user220688 Jul 15 '15 at 16:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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