Sorting a list in scheme

Question

How do write a sorting algorithm that returns a list into increasing order.

ex: '(1 3 5 2 9) returns '(1 2 3 5 9)

Solution 1

Most Scheme implementations come with a procedure to sort lists. If your implementation does not provide one, it is not difficult to roll one on your on. Here is an implementation of the quick-sort algorithm:

> (define (qsort e)
  (if (or (null? e) (<= (length e) 1)) e
      (let loop ((left null) (right null)
                   (pivot (car e)) (rest (cdr e)))
            (if (null? rest)
                (append (append (qsort left) (list pivot)) (qsort right))
               (if (<= (car rest) pivot)
                    (loop (append left (list (car rest))) right pivot (cdr rest))
                    (loop left (append right (list (car rest))) pivot (cdr rest)))))))
> (qsort  '(1 3 5 2 9))
=> (1 2 3 5 9)

Solution 2

SRFI 95 provides a sorting library. Many Scheme implementation also have sorting libraries built in, though not all of them conform to the SRFI 95 interface.

---

If you need to write your own implementation (for homework, say), then you should use one of the standard sorting algorithms like mergesort or quicksort. However, both of those algorithms are vector-based algorithms, so you will need to copy the list to a vector, sort that, then copy it back to a list. (You may find SRFI 43 useful for vector manipulation operations, especially vector-swap! for swapping two elements of a vector.)

There may be algorithms that are suited for sorting a linked list directly. I'm not au fait with them, so I won't comment on them further.