CODEWITHSUNDEEP
scheme
Joe
Joe

Reputation: 105

Sorting a list in scheme

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)

Upvotes: 4

Views: 12629

Answers (2)

Vijay Mathew
Vijay Mathew

Reputation: 27164

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)

Upvotes: 6

C. K. Young
C. K. Young

Reputation: 223003

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.

Upvotes: 1

Related Questions