Results 1 to 3 of 3

Math Help - sorting of unordered elements - worst case scenario

  1. #1
    Newbie
    Joined
    Apr 2011
    Posts
    4

    sorting of unordered elements - worst case scenario

    Hi, I have a problem which seems easy but is giving me a hard time, I'd really appreciate some input.

    Assuming I have n objects and have to put them in order, how many comparisons between each 2 objects do I have to make in the worst case scenario?

    I made some attempts but find it difficult to come up with a generic formula
    1 object -> 0 comparisons
    2 objects -> 1 comparison suffices
    3 objects -> first do 2 objects (1 comparison) and then compare remaining object with bigger/smaller element (1 comparison), if smaller/bigger then compare with the remaining object (1 comparison). In total 3 steps.
    4 objects -> as in 3 objects (3 comparisons), then compare remaining object with the middle point. If it's smaller/bigger then compare with smallest/largest element. Total of 3+2=5 steps
    5 objects -> as in 4 objects (5 comparisons). Find the middle point (2nd or 3rd object, 1 comparison). It's the last step of ordering 3 objects (when 2 are already ordered and we need to find the place of the final element, 2 steps). Total of 5+1+2=8 comparisons.

    Generally the story is: Use the number of steps used for n-1. Then find the middle of the n-1 string (if it's even it does not matter whether I take (n-1)/2 or (2+1)/2). Then find the middle of this string and repeat the process until we are left with case of ordering 2 objects.

    Please tell me if the general formula for this exist and if so I'd appreciate any hints
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769
    Each comparison-based sorting algorithm has the worst complexity of \Omega(n\log n). (For big-Omega and similar notations see this Wikipedia page.) For a proof, see these (PPT) or these (PDF) lecture slides or Google for 'sorting algorithm worst case nlogn "decision tree"'.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2011
    Posts
    4

    Re: sorting of unordered elements - worst case scenario

    Thanks, that gave a complete answer to my question.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: December 7th 2010, 07:17 AM
  2. Sorting Elements of Set Before Working On it?
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 20th 2010, 06:59 AM
  3. Worst case for prime factorisation
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: December 16th 2009, 01:04 AM
  4. ordered and unordered partitions
    Posted in the Statistics Forum
    Replies: 2
    Last Post: October 12th 2009, 11:39 AM

Search Tags


/mathhelpforum @mathhelpforum