Next: , Previous: Object Properties, Up: Utility Functions

24.3 Sorting

Sorting is very important in computer programs. Therefore, Guile comes with several sorting procedures built-in. As always, procedures with names ending in ! are side-effecting, that means that they may modify their parameters in order to produce their results.

The first group of procedures can be used to merge two lists (which must be already sorted on their own) and produce sorted lists containing all elements of the input lists.

— Scheme Procedure: merge a b less?
— C Function: scm_merge (a, b, less?)

Merge two already sorted lists into one. Given two lists a and b, such that both (sorted? a less?) and (sorted? b less?) are true, return a new list in which the elements of a and b are stably interleaved so that (sorted? (merge a b less?) less?) would be true. Note: This procedure does not accept vectors.

— Scheme Procedure: merge! a b less?
— C Function: scm_merge_x (a, b, less?)

Take two lists a and b such that (sorted? a less?) and (sorted? b less?) are true, and return a new list in which the elements of a and b are stably interleaved so that (sorted? (merge a b less?) less?) would be true. This is the destructive variant of merge. Note: This procedure does not accept vectors.

The following procedures can operate on sequences which are either vectors or list. According to the given arguments, they return sorted vectors or lists, respectively. The first of the following procedures determines whether a sequence is already sorted, the other sort a given sequence. The variants with names starting with stable- are special in that they maintain a special property of the input sequences: If two or more elements are the same according to the comparison predicate, they are left in the same order as they appeared in the input.

— Scheme Procedure: sorted? items less
— C Function: scm_sorted_p (items, less)

Return #t iff items is a list or a vector such that for all 1 <= i <= m, the predicate less returns true when applied to all elements i - 1 and i.

— Scheme Procedure: sort items less
— C Function: scm_sort (items, less)

Sort the sequence items, which may be a list or a vector. less is used for comparing the sequence elements. This is not a stable sort.

— Scheme Procedure: sort! items less
— C Function: scm_sort_x (items, less)

Sort the sequence items, which may be a list or a vector. less is used for comparing the sequence elements. The sorting is destructive, that means that the input sequence is modified to produce the sorted result. This is not a stable sort.

— Scheme Procedure: stable-sort items less
— C Function: scm_stable_sort (items, less)

Sort the sequence items, which may be a list or a vector. less is used for comparing the sequence elements. This is a stable sort.

— Scheme Procedure: stable-sort! items less
— C Function: scm_stable_sort_x (items, less)

Sort the sequence items, which may be a list or a vector. less is used for comparing the sequence elements. The sorting is destructive; i.e., the input sequence is modified to produce the sorted result. This is a stable sort.

The procedures in the last group only accept lists or vectors as input, as their names indicate.

— Scheme Procedure: sort-list items less
— C Function: scm_sort_list (items, less)

Sort the list items, using less for comparing the list elements. This is a stable sort.

— Scheme Procedure: sort-list! items less
— C Function: scm_sort_list_x (items, less)

Sort the list items, using less for comparing the list elements. The sorting is destructive; i.e., the input list is modified to produce the sorted result. This is a stable sort.

— Scheme Procedure: restricted-vector-sort! vec less startpos endpos
— C Function: scm_restricted_vector_sort_x (vec, less, startpos, endpos)

Sort the vector vec in place, using less for comparing elements. startpos and endpos delimit the range of the vector to be sorted.