Results 1 to 3 of 3

Math Help - Sort Algorithm

  1. #1
    Junior Member
    Joined
    Mar 2013
    From
    u.s.
    Posts
    50

    Sort Algorithm

    How might someone with (much) more knowledge explain this?

    A common result in the analysis of sorting algorithms is that for n elements, the best average-case behavior of any sort algorithm—based solely on comparisons—is O(n log n).

    How might a sort algorithm beat this average-case behavior based on additional prior knowledge of the data elements?

    What sort of speed-up might be anticipated for such an algorithm? In other words, does it suddenly become O(n), O(n log n) or something similar?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773

    Re: Sort Algorithm

    If you are sorting nonnegative numbers and you know the maximum possible number M, then you can do as follows. Declare an array output of M elements, fill it with zeroes, go through a given array input and for each number k in input, assign 1 to the kth element of output. After that, go through output in the order of increasing (or decreasing) indices and print indices where 1 is stored. The time complexity of this algorithm is O(M). If the length of input is n and if M <= c * n for some constant c that does not depend on n and M, then the complexity is also O(n).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Mar 2013
    From
    u.s.
    Posts
    50

    Re: Sort Algorithm

    Thank you for that explanation emakarov! Appreciate it.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. What sort of DE is this?
    Posted in the Differential Equations Forum
    Replies: 6
    Last Post: November 1st 2010, 02:24 AM
  2. Proof Shuttle Sort is a quadratic order algorithm.
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 11th 2010, 12:50 PM
  3. More max/min (sort of)
    Posted in the Calculus Forum
    Replies: 4
    Last Post: October 23rd 2009, 02:39 PM
  4. Sort this numbers
    Posted in the Algebra Forum
    Replies: 2
    Last Post: August 23rd 2009, 04:36 AM
  5. Merge Sort Algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 20th 2007, 10:33 PM

Search Tags


/mathhelpforum @mathhelpforum