Re: Heapsort Complexity Analysis

Message-ID	<4E827395.6FE0@mindspring.com> (permalink)
Date	2011-09-27 21:08 -0400
From	pete <pfiland@mindspring.com>
Organization	PF
Newsgroups	comp.programming, comp.lang.c, comp.lang.c++
Subject	Re: Heapsort Complexity Analysis
References	<j5rmja$6nj$1@dont-email.me>

Cross-posted to 3 groups.

Show all headers | View raw

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

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