[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: srfi-32@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx*Subject*: quick-sort3!*From*: shivers@xxxxxxxxxxxxx*Date*: Wed, 24 Jul 2002 13:09:22 -0400*Delivered-to*: srfi-32@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx*Reply-to*: shivers@xxxxxxxxxxxxx

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).

- Prev by Date:
**Three-way action** - Next by Date:
**SRFI 32** - Previous by thread:
**Three-way action** - Next by thread:
**SRFI 32** - Index(es):