Author 
Message 
Myron A Calho #1 / 3

a sorting question...
This isn't directly related to fortran or Fortran (although any implementation I make will use F77!) If I understand the definition of "stability" when applied to a sort, when a sort is "stable", items which have identical keys remain in their original relative positions. I know the ubiquitous (and poor) bubble sort is stable and I think that sorts which compare keys separated by VARYING distances can NOT be stable (this eliminates the Comb sort), but can anyone say anything about the stability of the following sorts? Heap, Insertion, Merge, Quick, Selection, and Shell (and any others anyone might wish to add) Myron.  Five boxes preserve our freedoms: soap, ballot, witness, jury, and cartridge PhD EE (retired). "Barbershop" tenor. CDL(PTX). W0PBV. (785) 5394448 NRA Life Member and Certified Instructor (Home Firearm Safety, Rifle, Pistol)

Sun, 01 May 2005 02:41:02 GMT 


Nick Maclar #2 / 3

a sorting question...
Quote: >This isn't directly related to FORTRAN or Fortran >(although any implementation I make will use F77!) >If I understand the definition of "stability" when applied to a sort, >when a sort is "stable", items which have identical keys remain in their >original relative positions. I know the ubiquitous (and poor) bubble >sort is stable and I think that sorts which compare keys separated by >VARYING distances can NOT be stable (this eliminates the Comb sort), >but can anyone say anything about the stability of the following sorts? > Heap, Insertion, Merge, Quick, Selection, and Shell > (and any others anyone might wish to add)
I have never worked out what is meant by insertion and selection sorts, as they (and bubble sort) all appear to be just examples of a generic class of O(N^2) sorts. Treating them as very distinct sorts is a recent aberration (c. 25 years back). All sorts can be made stable by adding an extra field to the key, but list merge can be made stable without that. None of heap, quick and Shell sorts can, unless there is a very subtle trick that has escaped me for many years. Both forms of radix sort can, as well (one is now often called bucket sort), and that result has been known since time immemorial. The property was used in the old, preelectronic and possibly even preelectric card sorting machines. Regards, Nick Maclaren, University of Cambridge Computing Service, New Museums Site, Pembroke Street, Cambridge CB2 3QH, England.
Tel.: +44 1223 334761 Fax: +44 1223 334679

Sun, 01 May 2005 04:08:02 GMT 


James Gile #3 / 3

a sorting question...
... Quote: > If I understand the definition of "stability" when applied to a sort, > when a sort is "stable", items which have identical keys remain in their > original relative positions. I know the ubiquitous (and poor) bubble > sort is stable and I think that sorts which compare keys separated by > VARYING distances can NOT be stable (this eliminates the Comb sort), > but can anyone say anything about the stability of the following sorts? > Heap, Insertion, Merge, Quick, Selection, and Shell > (and any others anyone might wish to add)
Note that any sorting method can be made stable by including the original position in the collection as the lowestsignificance part of the key. A variant of this: suppose the data to be sorted is physically in some order to begin with (that is, its initial order in not specified by links) and your sort produces a linkedlist (without actually moving the data) which specifies a sorted permutation of the data. The stable sorted permutation can then be constructed with a single pass through the list and reordering adjacent links to identical keys so the links themselves are in order. There are a number of other variations to the idea. Since stability can usually be recovered, I've usually not considered it an important issue. In most cases you don't need stability, and in the rest you usually still want the fastest sort for your problem  you then recover stability as needed.  J. Giles

Sun, 01 May 2005 04:16:12 GMT 


