Results 1 to 2 of 2

Math Help - sorting fraction with linear time algorithm

  1. #1
    Newbie
    Joined
    May 2008
    Posts
    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by modster View Post
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Sorting by Covered-Rest Distance and Time
    Posted in the Statistics Forum
    Replies: 0
    Last Post: October 15th 2011, 12:56 PM
  2. Algorithm(Searching and Sorting)
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 21st 2009, 11:41 PM
  3. Question on algorithm (Sorting)
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 26th 2009, 08:35 AM
  4. Fastest sorting algorithm
    Posted in the Discrete Math Forum
    Replies: 18
    Last Post: April 7th 2008, 08:31 PM
  5. sorting algorithm
    Posted in the Advanced Math Topics Forum
    Replies: 2
    Last Post: November 26th 2007, 07:12 AM

Search Tags


/mathhelpforum @mathhelpforum