# Can someone help me with this computer science question?



## modster (Jun 16, 2007)

Grr.. I am pulling my hair out right now. I would really appreciate if someone can give me some help. The problem is given N fractions with numerators and denominators are integers between 1 and N, how do you sort it in linear time? Thanks in advance.


----------



## BiscuitSlayer (Apr 19, 2008)

Find the common denominator and then sort them by size?

1/8 , 1/4, 1/16, 5/32

4/32, 8/32, 2/32, 5/32 =

2/32, 4/32, 5/32, 8/32

Or am I missing the point?


----------



## bdement (Jun 4, 2007)

I think: Multiply each denominator (Di) together to get the common denominator (D). Multiply each numerator by D/Di. Sort the numerators.


----------



## modster (Jun 16, 2007)

BiscuitSlayer said:


> Find the common denominator and then sort them by size?
> 
> 1/8 , 1/4, 1/16, 5/32
> 
> ...


I was thinking about this, but finding lcm would use more than linear time?


----------



## orion2001 (Mar 20, 2008)

Wouldn't bdement's suggestion be implementable in linear time?

Note- In his suggestion you aren't finding the LCM, just a particular common multiple which requires no calculation overhead beyond multiplying all the numbers out together


----------



## modster (Jun 16, 2007)

Well, multiply everything with a common multiple would certainly make everything integers. The problem is the sorting algorithm would have a runtime proportional to the range, with is not N anymore after the multiplying.


----------

