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

quick-sort3!



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