[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

6.24 Comparison and sorting

Function: compare obj1 obj2

A general comparison procedure. Returns -1 if obj1 is less than obj2, 0 if obj1 is equal to obj2, and 1 if obj1 is greater than obj2. Signals an error if obj1 and obj2 are incomparable.

Some built-in types are handled by this procedure reflecting “natural” order of comparison. Other built-in types are generally uncomparable. For Scheme-defined classes, this procedure calls a generic function object-compare.

Generic Function: object-compare obj1 obj2

Specializing this generic function extends compare procedure for user-defined classes.

Function: sort seq :optional cmpfn
Function: sort! seq :optional cmpfn

Sorts elements in a sequence seq (a list or a vector) in ascending order and returns the sorted sequence. sort! destructively reuses the original sequence. The sorting order is specified by cmpfn, which is a procedure takes two elements of seq, and returns #t if the first argument strictly precedes the second.

Note that it is not guaranteed that, after sort!, seq points to a sorted sequence. if seq is a list, the first pair of the original seq may no longer be the first in the sorted sequence. Always use the returned value of sort!.

 
(sort '(("Chopin" "Frederic")
        ("Liszt" "Franz")
        ("Alkan" "Charles-Valentin"))
      (lambda (x y) (string<? (car x) (car y))))
  ⇒ (("Alkan" "Charles-Valentin")
      ("Chopin" "Frederic")
      ("Liszt" "Franz"))

When cmpfn is omitted, the compare procedure is used to determine which element is less.

In the current implementation, quicksort and heapsort algorithm is used when cmpfn is omitted, and merge sort algorithm is used when cmpfn is given. This might be changed later.

If you want to keep a sorted set of objects to which you add objects one at at time, you can also use treemaps (See section Treemaps).

Function: stable-sort seq :optional cmpfn
Function: stable-sort! seq :optional cmpfn

Sort a sequence seq (a list or a vector), using stable sort algorithm (currently they are using merge sort). The sorting order is specified by cmpfn, which is a procedure takes two elements of list, and returns #t if the first argument strictly precedes the second.

Function: sort-by seq key :optional cmpfn
Function: sort-by! seq key :optional cmpfn
Function: stable-sort-by seq key :optional cmpfn
Function: stable-sort-by! seq key :optional cmpfn

Sorts seq, by comparing the key values obtained by applying the key procedure to each element of seq. The code (stable-sort-by seq key cmp) returns the same result as the following code:

 
(stable-sort seq (lambda (a b) (cmp (key a) (key b))))

Besides more compact notation, sort-by family procedures guarantee that key procedure is called at most the number of elements in seq. In the above example using stable-sort, key may be called nlogn or even more times where n is the number of elements in seq. So sort-by etc. are good if the key procedure is a relatively heavy operation.

The trade-off is the space; sort-by family consumes extra space to save all the key values, which is proportional to the number of elements.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]

This document was generated by Shiro Kawai on May 28, 2012 using texi2html 1.82.