[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
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.
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).