This page is part of the web mail archives of SRFI 32 from before July 7th, 2015. The new archives for SRFI 32 contain all messages, not just those from before July 7th, 2015.
Here is the new text including the three-way quick sort.
I have not uploaded the changed SRFI, as I have more new
comments to process first.
-Olin
vector-quick-sort-lib - vector quick sort
quick-sort v < [start end] -> vector
quick-sort! v < [start end] -> unspecific
quick-sort3! v c [start end] -> unspecific
These procedures sort their data using quick sort,
which is not a stable sorting algorithm.
QUICK-SORT returns a vector of length END-START.
QUICK-SORT! is in-place, leaving its result in V[start,end).
QUICK-SORT3! is a variant of quick-sort that takes a three-way
comparison function C. C compares a pair of elements and returns
an exact integer whose sign indicates their relationship:
(c x y) < 0 => x<y
(c x y) = 0 => x=y
(c x y) > 0 => x>y
To help remember the relationship between the sign of the result and
the relation, use the function - as the model for C: (- x y) < 0
means that x < y; (- x y) > 0 means that x > y.
The extra discrimination provided by the three-way comparison can
provide significant speedups when sorting data sets with many duplicates,
especially when the comparison function is relatively expensive (e.g.,
comparing long strings).