| From: "Marcin 'Qrczak' Kowalczyk" <qrczak_at_knm.org.pl>
| Date: Wed, 04 Oct 2006 00:38:03 +0200
|
| Sven.Hartrumpf_at_FernUni-Hagen.de writes:
|
| > If some people are really interested in this they should revive
| > SRFI-32, which has been withdrawn at a - let's say - 90%
| > completion level.
|
| I can't believe that R6RS needs 28 procedures about sorting.
| I propose four:
|
| (sort lst <)
| (sort-by lst get-key <)
| (vector-sort! vec <)
| (vector-sort-by! vec get-key <)
The sort-and-merge SRFI I have submitted to the SRFI-editors
(
http://swiss.csail.mit.edu/~jaffer/srfi/srfi-new.html) has only 5:
Function: sorted? sequence less?
Function: sorted? sequence less? get-key
Function: sort sequence less?
Function: sort sequence less? get-key
Function: sort! sequence less?
Function: sort! sequence less? get-key
Function: merge list1 list2 less?
Function: merge list1 list2 less? get-key
Function: merge! list1 list2 less?
Function: merge! list1 list2 less? get-key
| All stable, with the algorithm unspecified (recommended N*log(N)
| complexity).
Okay.
| The "!" variants sort in place.
Yes.
| The key should be extracted exactly once for each element.
Because there are potentially more than O(N) comparisons, keys are
potentially accessed more than once. So the sort routines would need
to allocate O(N) storage to hold the keys to meet this requirement.
Received on Thu Oct 12 2006 - 19:07:14 UTC