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> Date: Tue, 27 Sep 2011 21:08:37 -0400 From: pete 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: 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 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