Re: Heapsort Complexity Analysis

Path	csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!border3.nntp.dca.giganews.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!nntp.earthlink.com!news.earthlink.com.POSTED!not-for-mail
NNTP-Posting-Date	Tue, 27 Sep 2011 20:08:38 -0500
Message-ID	<4E827395.6FE0@mindspring.com> (permalink)
Date	Tue, 27 Sep 2011 21:08:37 -0400
From	pete <pfiland@mindspring.com>
Reply-To	pfiland@mindspring.com
Organization	PF
X-Mailer	Mozilla 3.04Gold (WinNT; I)
MIME-Version	1.0
Newsgroups	comp.programming, comp.lang.c, comp.lang.c++
Subject	Re: Heapsort Complexity Analysis
References	<j5rmja$6nj$1@dont-email.me>
Content-Type	text/plain; charset=us-ascii
Content-Transfer-Encoding	7bit
Lines	66
X-Usenet-Provider	http://www.giganews.com
NNTP-Posting-Host	4.154.219.202
X-Trace	sv3-74rMlxkD70//oT/3htwa1FrokshgH+Hp84IbE3JvV2QN7AEBKVmbA8KSQERm3utlFmYnQQLAtoSt//V!TqQDyTmdCZIozF0M24KF18yWpGbn3ec/eTDVxsgtY0Uj/O29iCjLbOHftVnGN0In0231qovhYUr6!ENCy0IbmqvE=
X-Abuse-and-DMCA-Info	Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info	Otherwise we will be unable to process your complaint properly
X-Postfilter	1.3.40
X-Original-Bytes	3039
Xref	x330-a1.tempe.blueboxinc.net comp.programming:875 comp.lang.c:11032 comp.lang.c++:10556

Cross-posted to 3 groups.

Show key headers only | 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