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=-2.9 required=5.0 tests=BAYES_00,MAILING_LIST_MULTI autolearn=unavailable autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,cda33fc7f63c2885 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2002-01-08 11:57:06 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!fr.clara.net!heighliner.fr.clara.net!freenix!enst!enst.fr!not-for-mail From: "Steven Deller" Newsgroups: comp.lang.ada Subject: RE: list strawman Date: Tue, 8 Jan 2002 14:54:05 -0500 Organization: ENST, France Sender: comp.lang.ada-admin@ada.eu.org Message-ID: Reply-To: comp.lang.ada@ada.eu.org NNTP-Posting-Host: marvin.enst.fr Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit X-Trace: avanie.enst.fr 1010519824 80285 137.194.161.2 (8 Jan 2002 19:57:04 GMT) X-Complaints-To: usenet@enst.fr NNTP-Posting-Date: Tue, 8 Jan 2002 19:57:04 +0000 (UTC) To: Return-Path: X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook, Build 10.0.2627 Importance: Normal In-Reply-To: <3c3b13ba$0$212$626a54ce@news.free.fr> X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400 Errors-To: comp.lang.ada-admin@ada.eu.org X-BeenThere: comp.lang.ada@ada.eu.org X-Mailman-Version: 2.0.6 Precedence: bulk List-Help: List-Post: List-Subscribe: , List-Id: comp.lang.ada mail<->news gateway List-Unsubscribe: , Errors-To: comp.lang.ada-admin@ada.eu.org X-BeenThere: comp.lang.ada@ada.eu.org Xref: archiver1.google.com comp.lang.ada:18663 Date: 2002-01-08T14:54:05-05:00 > -----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