SRFI 132 - Sort Libraries

The (srfi 132) library implements the the API for a full-featured sort toolkit.

See the SRFI document for more information.

list-delete-neighbor-dups

(list-delete-neighbor-dups = lis)

This procedure does not alter its input list, but its result may share storage with the input list.

list-delete-neighbor-dups!

(list-delete-neighbor-dups! = lis)

This procedure mutates its input list in order to construct its result. It makes only a single, iterative, linear-time pass over its argument, using set-cdr!s to rearrange the cells of the list into the final result — it works “in place.” Hence, any cons cell appearing in the result must have originally appeared in the input.

list-merge

(list-merge < lis1 lis2)

This procedure does not alter its inputs, and is allowed to return a value that shares a common tail with a list argument.

All four merge operations are stable: an element of the initial list lis1 or vector v1 will come before an equal-comparing element in the second list lis2 or vector v2 in the result.

list-merge!

(list-merge! < lis1 lis2)

This procedure makes only a single, iterative, linear-time pass over its argument lists, using set-cdr!s to rearrange the cells of the lists into the list that is returned — it works “in place.” Hence, any cons cell appearing in the result must have originally appeared in an input. It returns the sorted input.

Additionally, list-merge! is iterative, not recursive — it can operate on arguments of arbitrary size without requiring an unbounded amount of stack space. The intent of this iterative-algorithm commitment is to allow the programmer to be sure that if, for example, list-merge! is asked to merge two ten-million-element lists, the operation will complete without performing some extremely (possibly twenty-million) deep recursion.

All four merge operations are stable: an element of the initial list lis1 or vector v1 will come before an equal-comparing element in the second list lis2 or vector v2 in the result.

list-sort

(list-sort < lis)

This procedure provides basic sorting.

list-sort!

(list-sort! < lis)

This procedure is a linear update operator and is allowed to alter the cons cells of the arguments to produce its results. A sorted list containing the same elements as lis is returned.

list-sorted?

(list-sorted? < lis)

Returns true iff the input list is in sorted order, as determined by <. Specifically, return #f iff there is an adjacent pair ... X Y ... in the input list such that Y < X in the sense of <.

list-stable-sort

(list-stable-sort < lis)

Provides a stable sort.

list-stable-sort!

(list-stable-sort! < lis)

This procedure is a linear update operator and is allowed to alter the cons cells of the arguments to produce its results. A sorted list containing the same elements as lis is returned.

vector-delete-neighbor-dups

(vector-delete-neighbor-dups = v [ start [ end ] ])

This procedure does not alter its input vector, but rather newly allocates and returns a vector to hold the result.

vector-delete-neighbor-dups!

(vector-delete-neighbor-dups! = v [ start [ end ] ])

This procedure reuses its input vector to hold the answer, packing it into the index range [start, newend), where newend is the non-negative exact integer that is returned as its value. The vector is not altered outside the range [start, newend).

vector-find-median

(vector-find-median < v knil [ mean ])

This procedure does not alter its input vector, but rather newly allocates a vector to hold the intermediate result. Runs in O(n) time.

vector-find-median!

(vector-find-median! < v knil [ mean ])

This procedure reuses its input vector to hold the intermediate result, leaving it sorted, but is otherwise the same as vector-find-median. Runs in O(n ln n) time.

vector-merge

(vector-merge < v1 v2 [ start1 [ end1 [ start2 [ end2 ] ] ] ])

This procedure does not alter its inputs, and returns a newly allocated vector of length (end1 - start1) + (end2 - start2).

All four merge operations are stable: an element of the initial list lis1 or vector v1 will come before an equal-comparing element in the second list lis2 or vector v2 in the result.

vector-merge!

(vector-merge! < to from1 from2 [ start [ start1 [ end1 [ start2 [ end2 ] ] ] ] ])

This procedure writes its result into vector to, beginning at index start, for indices less than end, which is defined as start + (end1 - start1) + (end2 - start2). The target subvector to[start, end) may not overlap either of the source subvectors from1[start1, end1] and from2[start2, end2]. It returns an unspecified value.

All four merge operations are stable: an element of the initial list lis1 or vector v1 will come before an equal-comparing element in the second list lis2 or vector v2 in the result.

vector-select!

(vector-select! < v k [ start [ end ] ] )

This procedure returns the kth smallest element (in the sense of the < argument) of the region of a vector between start and end. Elements within the range may be reordered, whereas those outside the range are left alone. Runs in O(n) time.

vector-separate!

(vector-separate! < v k [ start [ end ] ] )

This procedure places the smallest k elements (in the sense of the < argument) of the region of a vector between start and end into the first k positions of that range, and the remaining elements into the remaining positions. Otherwise, the elements are not in any particular order. Elements outside the range are left alone. Runs in O(n) time. Returns an unspecified value.

vector-sort

(vector-sort < v [ start [ end ] ])

This procedure does not alter its inputs, but allocates a fresh vector as the result, of length end - start.

vector-sort!

(vector-sort! < v [ start [ end ] ])

Sort the data in-place and return an unspecified value.

vector-sorted?

(vector-sorted? < v [start [ end ] ])

Returns true iff the input vector is in sorted order, as determined by <. Specifically, return #f iff there is an adjacent pair ... X Y ... in the input vector such that Y < X in the sense of <. The optional start and end range arguments restrict vector-sorted? to examining the indicated subvector.

vector-stable-sort

(vector-stable-sort < v [ start [ end ] ])

This procedure does not alter its inputs, but allocates a fresh vector as the result, of length end - start.

vector-stable-sort!

(vector-stable-sort! < v [ start [ end ] ])

Sorts the data in-place. (But note that vector-stable-sort! may allocate temporary storage proportional to the size of the input — there are no known O(n lg n) stable vector sorting algorithms that run in constant space.) Returns an unspecified value.