GNU Info

(slib.info)Sorting

---

Next: Topological Sort Prev: Chapter Ordering Up: Sorting and Searching

---

Enter node , (file) or (file)node

Sorting
-------

  `(require 'sort)'

  Many Scheme systems provide some kind of sorting functions.  They do
not, however, always provide the _same_ sorting functions, and those
that I have had the opportunity to test provided inefficient ones (a
common blunder is to use quicksort which does not perform well).

  Because `sort' and `sort!' are not in the standard, there is very
little agreement about what these functions look like.  For example,
Dybvig says that Chez Scheme provides
     (merge predicate list1 list2)
     (merge! predicate list1 list2)
     (sort predicate list)
     (sort! predicate list)

while MIT Scheme 7.1, following Common LISP, offers unstable
     (sort list predicate)

TI PC Scheme offers
     (sort! list/vector predicate?)

and Elk offers
     (sort list/vector predicate?)
     (sort! list/vector predicate?)

  Here is a comprehensive catalogue of the variations I have found.

  1. Both `sort' and `sort!' may be provided.

  2. `sort' may be provided without `sort!'.

  3. `sort!' may be provided without `sort'.

  4. Neither may be provided.

  5. The sequence argument may be either a list or a vector.

  6. The sequence argument may only be a list.

  7. The sequence argument may only be a vector.

  8. The comparison function may be expected to behave like `<'.

  9. The comparison function may be expected to behave like `<='.

 10. The interface may be `(sort predicate? sequence)'.

 11. The interface may be `(sort sequence predicate?)'.

 12. The interface may be `(sort sequence &optional (predicate? <))'.

 13. The sort may be stable.

 14. The sort may be unstable.

  All of this variation really does not help anybody.  A nice simple
merge sort is both stable and fast (quite a lot faster than _quick_
sort).

  I am providing this source code with no restrictions at all on its use
(but please retain D.H.D.Warren's credit for the original idea).  You
may have to rename some of these functions in order to use them in a
system which already provides incompatible or inferior sorts.  For each
of the functions, only the top-level define needs to be edited to do
that.

  I could have given these functions names which would not clash with
any Scheme that I know of, but I would like to encourage implementors to
converge on a single interface, and this may serve as a hint.  The
argument order for all functions has been chosen to be as close to
Common LISP as made sense, in order to avoid NIH-itis.

  Each of the five functions has a required _last_ parameter which is a
comparison function.  A comparison function `f' is a function of 2
arguments which acts like `<'.  For example,

     (not (f x x))
     (and (f x y) (f y z)) == (f x z)

  The standard functions `<', `>', `char<?', `char>?', `char-ci<?',
`char-ci>?', `string<?', `string>?', `string-ci<?', and `string-ci>?'
are suitable for use as comparison functions.  Think of `(less? x y)'
as saying when `x' must _not_ precede `y'.

 - Function: sorted? sequence less?
     Returns `#t' when the sequence argument is in non-decreasing order
     according to LESS? (that is, there is no adjacent pair `... x y
     ...' for which `(less? y x)').

     Returns `#f' when the sequence contains at least one out-of-order
     pair.  It is an error if the sequence is neither a list nor a
     vector.

 - Function: merge list1 list2 less?
     This merges two lists, producing a completely new list as result.
     I gave serious consideration to producing a Common-LISP-compatible
     version.  However, Common LISP's `sort' is our `sort!' (well, in
     fact Common LISP's `stable-sort' is our `sort!', merge sort is
     _fast_ as well as stable!) so adapting CL code to Scheme takes a
     bit of work anyway.  I did, however, appeal to CL to determine the
     _order_ of the arguments.

 - Procedure: merge! list1 list2 less?
     Merges two lists, re-using the pairs of LIST1 and LIST2 to build
     the result.  If the code is compiled, and LESS? constructs no new
     pairs, no pairs at all will be allocated.  The first pair of the
     result will be either the first pair of LIST1 or the first pair of
     LIST2, but you can't predict which.

     The code of `merge' and `merge!' could have been quite a bit
     simpler, but they have been coded to reduce the amount of work
     done per iteration.  (For example, we only have one `null?' test
     per iteration.)

 - Function: sort sequence less?
     Accepts either a list or a vector, and returns a new sequence
     which is sorted.  The new sequence is the same type as the input.
     Always `(sorted? (sort sequence less?) less?)'.  The original
     sequence is not altered in any way.  The new sequence shares its
     _elements_ with the old one; no elements are copied.

 - Procedure: sort! sequence less?
     Returns its sorted result in the original boxes.  If the original
     sequence is a list, no new storage is allocated at all.  If the
     original sequence is a vector, the sorted elements are put back in
     the same vector.

     Some people have been confused about how to use `sort!', thinking
     that it doesn't return a value.  It needs to be pointed out that
          (set! slist (sort! slist <))

     is the proper usage, not
          (sort! slist <)

  Note that these functions do _not_ accept a CL-style `:key' argument.
A simple device for obtaining the same expressiveness is to define
     (define (keyed less? key)
       (lambda (x y) (less? (key x) (key y))))

and then, when you would have written
     (sort a-sequence #'my-less :key #'my-key)

in Common LISP, just write
     (sort! a-sequence (keyed my-less? my-key))

in Scheme.