RE: list strawman

["Steven Deller" <deller@smsail.com>]

> -----Original Message-----
> From: comp.lang.ada-admin@ada.eu.org 
> [mailto:comp.lang.ada-admin@ada.eu.org] On Behalf Of 
> Jean-Marc Bourguet
> Sent: Tuesday, January 08, 2002 10:44 AM
> To: comp.lang.ada@ada.eu.org
> Subject: Re: list strawman
> How do you do quicksort on a list?  quicksort assume random 
> access so you'll have O(n) space overhead. I'd use a merge 
> sort on a list which would have the same complexity as 
> quicksort and do not need random access.

Quick sort does not assume (or require) random access. As long as I can
split, splice, extract elements and add elements I can do quicksort.
(The nice online description and animation of quicksort that Ted D
supplied makes this obvious:
    http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/qsort.html 

Interestingly, using lists makes it possible to ensure that the
Quicksort is also stable -- the O(n) space required for making an
O(NlnN) sort into a stable sort is already inherent in the list
structure.

A Heapsort *does* require "indexed" access (which I presume is what you
mean by "random"), so it would not be a good candidate for list sorting.

Back in 1986 I wrote a sorting package for Rational (nee Verdix) that
provided several sorts and mentioned why others were not supplied.  Here
are some of the comments from that package, including a reference to a
nice "Taxomomy of Sorting" from 1985.  (I would note that the heapsort I
wrote is a slightly more efficient algorithm than described in Knuth,
uses Ada attributes to work with any array indices including enumeration
types, and encapsulates in Ada quite well -- there is a single routine
called "Almost_Heap_To_Heap" that is used both during the initialization
phase and the sorting phase, making the code quite succinct and easy to
understand.)

-- Provides several sorting algorithms and a permuting algorithm, which
are
-- generic with respect to
--   1. Element type in a List to be sorted, an arbitrary type.
--   2. Index type for indexing into the List, a discrete type.
--      A type List is defined from the Element type and the Index type.
--   3. A relation (Boolean result function) between Elements of the
List.
--      For an ascending sort, the relation should be True whenever the
--      first Element is strictly less than the second Element.  For a
--      descending sort, the relation should be True whenever the first
--      Element is strictly greater than the second Element.
-- Only "in-place" algorithms are provided, i.e. algorithms whose space
-- requirement is N or ( N + log_2(N)*e ), where e is some small value.
The
-- log_2(N)*e additional space is taken from the stack.
--
-- The following sorting algorithms are provided, and an indication is
given
-- about when the algorithm should be chosen:
-- 1. Quicksort (median-of-three): least average sort time of all, but
--    there are data organizations for which sorting time is O(N**2).
the
--    median-of-three approach is used for the split partition value, so
that
--    sorted data is NOT a worst case data organization (unlike the
basic
--    quicksort algorithm).
-- 2. Heapsort: guaranteed O(NlnN) time.  Note that the "heap" in this
--    algorithm applies to the type of data structure applied to the
--    list to be sorted; there is NO allocation of space from the heap.
-- 3. Insertion sort: one of the simplest sorts.  It is O(N**2) in time
--    complexity, but has the one advantage that it is stable, i.e.
elements
--    with equal values retain their order in the list.
--
-- The following sorting algorithms are NOT provided.  An indication of
-- why the algorithms are not provided is given.
-- 1. Shellsort (diminishing increments): This algorithm is consistently
--    bettered by Heapsort, and usually bettered by Quicksort.  Either
of
--    those should be used instead.
-- 2. Listmerge sort: This algorithm requires a special list that has a
--    link field in each element that can hold an index value.  Its
major
--    advantage is that it is a stable sort in O(NlnN) in time, i.e. it
--    makes a reasonable time-space tradeoff to achieve a stable sort.
--    However, its space requirements violate the "general element",
--    "in-place" sort requirements defined for this package.  A
reasonable
--    alternative to providing a stable sort in (NlnN) time is to add
--    a single field to each initial element, initialized to the value
--    of the element's position in the array, and make the "<" function
--    include a compare of this field if the original compared fields
--    are equal.  Thus equal elements are forced non-equal, and the
order
--    of equal elements in the array is maintained.
-- 3. Bubblesort.  This algorithm takes O(N**2) time, and has a higher
--    constant factor than insertion sort.
-- 4. Selectionsort.  This algorithm takes O(N**2), and is not stable
--    when done in-place with exchanges, unless considerable
complications
--    are added to the algorithm.
--
-- It is helpful to organize the sorting algorithms to aid
understanding.
-- The following taxonomy is based on the article:
--   An Inverted Taxonomy of Sorting Algorithms, Susan M. Merritt,
--   Communications of the ACM, Vol. 28, No. 1, January 1985, pp. 96-99.
--
-- All sorting algorithms are based on the abstraction "split into
parts,
-- sort the parts, join the sorted parts".  Specific sorting algorithms
are
-- conveniently classified as hard-split/easy-join or
easy-split/hard-join,
-- based on whether the "work" is done at the start or end of the
algorithm.
-- The abstract algorithm is clearly recursive.  Usual programming style
-- converts the recursions to iterations for speed.
--
-- If we independently specify the splitting criteria then we get the
-- following table:
--
--   Splitting criteria        hard-split/easy-join
easy-split/hard-join
--   ------------------        --------------------
--------------------
--   Equal-sized parts         Quicksort                 Merge Sort
--   One part is one element   Selection Sort            Insertion Sort
--   One element, in place     Bubble Sort               Sinking Sort
--
-- The Heapsort algorithm is viewed as a Selection Sort that minimizes
-- the comparisons to find the next element by using a data structure
-- (a heap).  The Shell Sort algorithm is viewed as a version of the
-- Insertion Sort that operates independently on various subsets of the
-- input data. An additional class of algorithms* may be viewed as
-- splitting criteria that are varying combinations of Quicksort with
-- Bubble Sort.  (Perhaps the combination of Merge Sort and Sinking Sort
-- would give rise to a similar set of algorithms.)
--
-- * A Class of Sorting Algorithms Based on Quicksort, Roger L.
Wainwright,
--   Communications of the ACM, Vol. 28, No. 4, April 1985, pp. 396-403.

Regards,
Steve