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: 109fba,baaf5f793d03d420 X-Google-Attributes: gid109fba,public X-Google-Thread: 103376,97188312486d4578 X-Google-Attributes: gid103376,public X-Google-Thread: fc89c,97188312486d4578 X-Google-Attributes: gidfc89c,public X-Google-Thread: 1014db,6154de2e240de72a X-Google-Attributes: gid1014db,public From: dewar@cs.nyu.edu (Robert Dewar) Subject: Re: Teaching sorts [was Re: What's the best language to start with?] Date: 1996/08/15 Message-ID: #1/1 X-Deja-AN: 174294257 references: <31FBC584.4188@ivic.qc.ca> <01bb83f5$923391e0$87ee6fce@timpent.airshields.com> <839708378snz@genesis.demon.co.uk> organization: Courant Institute of Mathematical Sciences newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada Date: 1996-08-15T00:00:00+00:00 List-Id: Robert Eachus said " There was a time when NO ONE knew how to build a heap in O(n) time, but it didn't last long. However, I was very interesting in sorting problems right then. Robert Dewer must have come along a little later, when treesort3 had almost completely replaced Heapsort. But they are two different (but closely related) algorithms. This is why I have been complaining about the mixup in names. " Well I will not argue further about ancient history, people can look that up for themselves. The important point is that it is been well known for 30 years that a heap can be constructed in O(N) time, so it is misleading to even suggest that it is an O N log N process. Perhaps the thing that is most importnat is to be aware that a heap can be constructed not just in O(N) compares, but if it is done right it takes just about N compares (i.e. the constant is 1). Furthermore, the subsequent sorting phase of heap sort can be done in about N log(N) compares (again with a constant of about 1), so that the approach is close to optimal. This is significant, because in this optimized form, heap sort is highly competitive with quicksort for the average case, and of course far superior for the worst case. And, since this thread hangs around comp.lang.ada, it is relevant to point out that GNAT provides this optimal heap sort algorithm. Look at the specs in g-gesora.ads and g-gesorg.ads, which are respectively access-to-subprogram (shared code) and generic (inlined code) codings of this algorithgm.