a sorting question... 
Author Message
 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) 539-4448
NRA Life Member and Certified Instructor (Home Firearm Safety, Rifle, Pistol)



Sun, 01 May 2005 02:41:02 GMT  
 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, pre-electronic and possibly even
pre-electric 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  
 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 lowest-significance 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 linked-list (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  
 
 [ 3 post ] 

 Relevant Pages 

1. Listbox sorting question

2. Another sorting question

3. CW2003 Browse Sort Question

4. newbie locale/ascii sort question

5. Sort Question

6. sort question

7. Sort Question

8. Homework: Sorting Question

9. Sort question

10. sorting question

11. list sort question

12. List sorting question

 

 
Powered by phpBB® Forum Software