Re: Heapsort Complexity Analysis

From	Gr <g@g.com>
Newsgroups	comp.programming, comp.lang.c, comp.lang.c++
Subject	Re: Heapsort Complexity Analysis
Date	2011-09-28 01:33 +0530
Organization	A noiseless patient Spider
Message-ID	<j5ta6g$b2e$1@dont-email.me> (permalink)
References	<j5rmja$6nj$1@dont-email.me> <f44c6b5f-478b-4e8a-af0c-8cff2bb9006c@i33g2000yqm.googlegroups.com> <MtSdndxLYM3xMhzTnZ2dnUVZ_vidnZ2d@earthlink.com>

Cross-posted to 3 groups.

Show all headers | View raw

On 27-09-2011 04:41 PM, Patricia Shanahan wrote:
> On 9/27/2011 2:45 AM, Gene wrote:
>> On Sep 27, 1:22 am, Gr<g...@g.com> wrote:
>>> Heapsort worst case complexity is obviously nLogN.
>>> However, what's the best case complexity?
>>> Can we consider that the siftup(fixup)& siftdown(fixdown) operations
>>> will be done in constant time, so the complexity of heapsort would be n?
>>> Is this correct - if not what's the best case scenario for heapsort?
>>
>> There are n! ways of ordering the input. Discovering the order of the
>> input is equivalent to sorting. (That is, if you know the order of
>> the input, it's trivial to sort. If you have a way of sorting, just
>> do it indirectly, and you have the original order of the input.) A
>> binary comparison can't eliminate more than half of the possible input
>> orderings at a time. So comparison sorting is Omega(log_2 n!) =
>> Omega(n log n). Look up "information theoretic sort time bound" for
>> the details. And prepare for people who will note this isn't a C
>> question.
>
>
> I'm not sure whether that is the answer to the question being asked.
>
> Consider bubble sort. If the input is already in sorted order, it does
> only n-1 comparisons.
>
> I think that may be what the OP meant by "best case scenario". Is there
> some input pattern that makes heapsort fast, the way pre-sorted input
> makes bubble sort fast?

Yes, that's what I was looking at.
Would the fixDown and/or fixDown become constant time for some 
particular order of input which would make the heapsort O(n) as a best 
case scenario.

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Heapsort Complexity Analysis Gr <g@g.com> - 2011-09-27 10:52 +0530
  Re: Heapsort Complexity Analysis Juha Nieminen <nospam@thanks.invalid> - 2011-09-27 07:14 +0000
  Re: Heapsort Complexity Analysis Gene <gene.ressler@gmail.com> - 2011-09-27 02:45 -0700
    Re: Heapsort Complexity Analysis Patricia Shanahan <pats@acm.org> - 2011-09-27 04:11 -0700
      Re: Heapsort Complexity Analysis Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-09-27 13:01 +0100
      Re: Heapsort Complexity Analysis Gene <gene.ressler@gmail.com> - 2011-09-27 05:53 -0700
      Re: Heapsort Complexity Analysis Gr <g@g.com> - 2011-09-28 01:33 +0530
  Re: Heapsort Complexity Analysis "christian.bau" <christian.bau@cbau.wanadoo.co.uk> - 2011-09-27 16:35 -0700
  Re: Heapsort Complexity Analysis pete <pfiland@mindspring.com> - 2011-09-27 21:08 -0400
  Re: Heapsort Complexity Analysis Kaz Kylheku <kaz@kylheku.com> - 2012-01-25 00:59 +0000
    Re: Heapsort Complexity Analysis "Ant" <not@home.today> - 2012-01-25 01:23 +0000

csiph-web