From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: fc89c,97188312486d4578 X-Google-Attributes: gidfc89c,public X-Google-Thread: 109fba,baaf5f793d03d420 X-Google-Attributes: gid109fba,public X-Google-Thread: 1014db,6154de2e240de72a X-Google-Attributes: gid1014db,public X-Google-Thread: 103376,97188312486d4578 X-Google-Attributes: gid103376,public From: thp@cs.ucr.edu (Tom Payne) Subject: Re: Teaching sorts [was Re: What's the best language to start with?] Date: 1996/08/15 Message-ID: <4uvj0d$hie@noise.ucr.edu>#1/1 X-Deja-AN: 174375629 references: <01bb7b06$311fabc0$87ee6fce@timpent.airshields.com> <31FBC584.4188@ivic.qc.ca> <01bb7da2$6c505ac0$96ee6fcf@timhome2> <01bb8027$de0e9c80$96ee6fcf@timhome2> <4u5a11$siv@mulga.cs.mu.OZ.AU> <01bb8342$88cc6f40$32ee6fcf@timhome2> <4u7grn$eb0@news1.mnsinc.com> <01bb83ad$29c3cfa0$87ee6fce@timpent.airshields.com> organization: University of California, Riverside newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada Date: 1996-08-15T00:00:00+00:00 List-Id: Robert I. Eachus wrote: : In article <839939925snz@genesis.demon.co.uk> Lawrence Kirby writes: : > > For heap sort, building the heap : > > is also an O(n log n) operation, since you maintain a heap. : > Wrong, you don't maintain a heap, you just build it. If you approach : > that correctly it is an O(n) operation. Quoting from Sedgewick: : > "... its can in fact be proven that the construction process takes : > linear time since so many small heaps are processed". : If you use the canonical heapsort it is O(2n) average, O(n log n) : worst case. (The worst case is when each card added to the bottom of : the heap propagates to the top, using the usual version of the sort, : or propagates to bottom in the other definition, where you start with : an unsorted list/heap and sort in place.) Keep in mind that the heap is growing as you add items. Each item gets propagated a distance that is not greater than its height from the leafs in the final tree. There are n/(2^i) nodes of height i, so the total number of steps is 1*n/2 + 2*n/4 + 3*n/8 + ... log(n)*n/(2^log(n)) which is o(n). Tom Payne (thp@cs.ucr.edu)