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

quick-sort3!

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