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

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.

*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):