Thread: sorting fraction with linear time algorithm

Given N fractions whose numerators and denominators are integers between 1 to N, how do you sort them in linear time?

The only linear time sort we have learned in class is bucket sort, so I guess this problem is bucket sort related? I have thought about using Farey Sequences but I don't think it would satisfy the linear time requirement. So any help?

Originally Posted by modster

Given N fractions whose numerators and denominators are integers between 1 to N, how do you sort them in linear time?

The only linear time sort we have learned in class is bucket sort, so I guess this problem is bucket sort related? I have thought about using Farey Sequences but I don't think it would satisfy the linear time requirement. So any help?

Use any linear time sort, but the comparisons (a,b)>(c,d) will be replaced by ac>bd (where (u,v) denotes the fraction u/v, and also I have assumed that a, b, c and d are all positive).

Or if you are not constained by the size of your integer type multiply all the numbers by N!, then sort.

RonL