Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #865 > unrolled thread

Heapsort Complexity Analysis

Back to article view | Back to comp.programming

Contents

  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

#865 — Heapsort Complexity Analysis

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?

[toc] | [next] | [standalone]

#866

In comp.lang.c++ Gr <g@g.com> wrote:
> Heapsort worst case complexity is obviously nLogN.
> However, what's the best case complexity?

  Every time the smallest (iow. first) element of the heap is removed,
the heap needs to be re-heapified, which is always a log(n) operation.
You need to do this n times.

[toc] | [prev] | [next] | [standalone]

#869

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.

[toc] | [prev] | [next] | [standalone]

#870

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?

Patricia

[toc] | [prev] | [next] | [standalone]

#871

Patricia Shanahan <pats@acm.org> writes:

> 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?

And that depends on the exact definition of the algorithm.  Any sort
that is O(n log(n)) can have a phase added that is O(n) with no effect
on the overall complexity.  As a result, any sort can test for sorted
input and have best case of n-1 compares.

Of course this is nit-picking since the OP makes it clear that they are
talking about the normal, unadorned, heapsort.  But if the question was
motivated by a desire to have no more that n-1 compares in the best
case, it becomes a tip (albeit one to be taken with a pinch of salt).

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#872

On Sep 27, 7:11 am, Patricia Shanahan <p...@acm.org> 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?
>
> Patricia
>
>

On second reading I guess you're right. I read "best case complexity"
as "lower asymptotic bound."  Certainly the normal array
implementation has no hope of an input ordering with constant number
of comparisions per element because it intentionally brings a leaf of
the heap to the top and sifts it back down on each iteration.  A
specially structured heap - with maybe some children intentionally
missing to limit sifting range - might change this.

[toc] | [prev] | [next] | [standalone]

#873

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.

[toc] | [prev] | [next] | [standalone]

#874

On Sep 27, 6: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?

Google for "smoothsort". A very clever variation of heapsort which is
O (n) for arrays that are sorted or almost sorted.

[toc] | [prev] | [next] | [standalone]

#875

Gr 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?

Considering three kinds of heapsort:
1    double sift down
2    double sift up
3    sift down, sift up

For an array of N elements, 
where all of the elements have the same value,
the double sift down heapsort will do 
less than (3 * N) comparisons to sort the array.

http://www.mindspring.com/~pfilandr/C/e_driver/

/* BEGIN e_driver.c program output */

Counting comparisons and MOV's for 3 different sorting functions.
Sorting arrays of N number of elements.

Distribution #1: Constant
       N             hsortx1              hsort6              hesort
              CMPS      MOVS      CMPS      MOVS      CMPS      MOVS
    1000      2994      5993     10458     14965      9967     11975
Total cmps
  hsortx1:      2994  heapsort, siftdown
   hsort6:     10458  heapsort, siftup
   hesort:      9967  hesort, siftdown and siftup
Total movs
  hsortx1:      5993
   hsort6:     14965
   hesort:     11975

/* END e_driver.c program output */




/* BEGIN e_driver.c program output */

Counting comparisons and MOV's for 3 different sorting functions.
Sorting arrays of N number of elements.

Distribution #1: Constant
       N             hsortx1              hsort6              hesort
              CMPS      MOVS      CMPS      MOVS      CMPS      MOVS
 1000000   2999994   5999993  20451392  24951412  19951405  21951423
Total cmps
  hsortx1:   2999994  heapsort, siftdown
   hsort6:  20451392  heapsort, siftup
   hesort:  19951405  hesort, siftdown and siftup
Total movs
  hsortx1:   5999993
   hsort6:  24951412
   hesort:  21951423

/* END e_driver.c program output */

-- 
pete

[toc] | [prev] | [next] | [standalone]

#1269

On 2011-09-27, Gr <g@g.com> wrote:
> Heapsort worst case complexity is obviously nLogN.
> However, what's the best case complexity?

You know how to connect to an NNTP server, but not use Google?

What institution let you roam out into the streets? :)

Millions of people successfully Google every day who have never heard of
Usenet.

The Wikipedia page on Heapsort has the following table:

Class                           Sorting algorithm
Data structure                  Array
Worst case performance          O(n log  n)
Best case performance           Ω(n),O(n log  n)[1]
Average case performance        O(n log  n)
Worst case space complexity     O(n) total, O(1) auxiliary

This is wrong. Or rather, the omega(n) lower bound, while technically true, is
not tight enough to be the useful answer. Yes, it's obvious that heapsort
works no *faster* than omega(n).

A citation is given: [1] pointing to "The Analysis of Heapsort", by R. Schaffer
and R. Sedgewick. This text is not available for free, but from what is stated
in the abstract, it is obvious that the paper gives a tighter analysis.

Furthermore, there is this StackOverflow posting by someone summarizing the
main arguments from the paper:

http://stackoverflow.com/questions/4589988/lower-bound-on-heapsort

It looks as though heap sort is theta(n log n). I.e. it has no better
or worse behavior for any inputs.

All courtesy of using search engines.

Before you go, let's burp you, too, and change your diaper!

[toc] | [prev] | [next] | [standalone]

#1270

"Kaz Kylheku" wrote:

> On 2011-09-27, Gr wrote:

[stuff] note the date.

> Before you go, let's burp you, too, and change your diaper!

He went four months ago, you twit (seeing as we're trading insults).

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web