ech@cbnewsk.ATT.COM (ned.horvath) (04/07/90)
From article <1990Apr5.150213.14655@ux1.cso.uiuc.edu>, by dorner@pequod.cso.uiuc.edu (Steve Dorner): > But it requires other space overhead that QuickSort does not; either explicit > heap pointers, or a table that is (potentially) twice as large as it has > to be (if n is a power of 2 or slightly more). Or is my memory failing? > > One advantage that has gone unmentioned is that Heapsort is stable; it doesn't > change the order of equal keys. Quicksort is decidedly unstable, which can > be a BAD THING. Heapsort uses only fixed space for its index variables (a purist would say O(logN) since an index needs logN bits for an array of size N), assuming you're sorting an array of fixed-size objects. Since that's what qsort operates on, I assume that's the name of the game. Heapsort operates on arrays of arbitrary size, not just sizes near 2^n. Heapsort is NOT stable. Neither is Quicksort. I know of no "tweaks" to either that are. Straight-insertion sort is stable, but may be O(N^2). I know a simple recursive in-place stable sort, but it's O(N(logN)^2). I know an NlogN inplace stable sort that's so hairy it got me a PhD back in the 70's... (you DON'T want to know). =Ned Horvath=
amanda@mermaid.intercon.com (Amanda Walker) (04/09/90)
In article <2368@cbnewsk.ATT.COM>, ech@cbnewsk.ATT.COM (ned.horvath) writes: > Heapsort is NOT stable. Neither is Quicksort. I know of no "tweaks" > to either that are. As several people have pointed out to me in email, heapsort is not an inherently stable sort. I tend to forget this, because there is a class of cases where it can be easily made so, and most of my applications of sorting have fallen into this class. To wit: Heapsort (and, in fact, almost any sorting algorithm) can be made stable as long as you have a way to determine the original ordering of two elements that compare as "equal", and you use this ordering to break any ties. In my case, I usually sort an array of pointers to my actual data elements, which are usually contiguous. This means that I can compare the values of the pointers themselves to determine the original ordering of any pair of elements, thus breaking the tie and making the sort stable. This amounts to using a comparison function that never actually returns "equal", making the inherent stability of the sorting algorithm irrelevant. Since I build the arrays of pointers anyway (principally for increased speed, since exchanges only use pointers instead of exchanging actual data elements), I get get stability pretty much for "free". Note that building an index of this sort (pun? what pun?) only requires space and time proportional to the number if elements. -- Amanda Walker, InterCon Systems Corporation -- "Y'know, you can't have, like, a light, without a dark to stick it in... You know what I'm sayin'?" --Arlo Guthrie