# Thread: sorting fraction with linear time algorithm

1. ## 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?

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

#### Search Tags

algorithm, fraction, linear, sorting, time 