Сортировка списка в схеме

Question

Как написать алгоритм сортировки, который возвращает список в порядке возрастания.

ex: '(1 3 5 2 9) возвращает '(1 2 3 5 9)

Answer 1

В большинстве реализаций Scheme есть процедура сортировки списков. Если ваша реализация не предоставляет такую ​​возможность, нетрудно накатить ее на себя. Вот реализация алгоритма быстрой сортировки:

> (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)

Answer 2

SRFI 95 предоставляет библиотеку сортировки.Многие реализации Scheme также имеют встроенные библиотеки сортировки, хотя не все они соответствуют интерфейсу SRFI 95.

---

Если вам нужно написать собственную реализацию (скажем, для домашней работы), вам следует использоватьодин из стандартных алгоритмов сортировки, таких как сортировка слиянием или быстрая сортировка.Однако оба этих алгоритма являются векторными, поэтому вам нужно будет скопировать список в вектор, отсортировать его, а затем скопировать обратно в список.(Вы можете найти SRFI 43 полезным для операций с вектором, особенно vector-swap! для замены двух элементов вектора.)

Могут быть подходящие алгоритмыдля сортировки связанного списка напрямую.Я не знаком с ними, поэтому я не буду комментировать их дальше.