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

Question

Хорошо, я пытаюсь составить список и отсортировать его от наибольшего к наименьшему.

Example:
> (maxheap (list 5 6 2 1 18 7))
;output:
> (18 7 6 5 2 1)

Итак, вот что я получил:

(define (mkmaxheap heaplist)
  (let ((max (mymax(heaplist))))
  ;mymax is a func that returns max number, it works

    (let (( head (car heaplist)) (tail (cdr heaplist)))
      (if (null? tail)
         newlist))))

Это все, что я мог получить для компиляции, весь другой код, который я написал, не удался. Любая помощь в решении этой проблемы будет принята с благодарностью.

Answer 1

Вы должны четко сформулировать стратегию, которую вы хотите использовать для создания отсортированного списка. Это что-то вроде этого?

• Найдите максимальное количество в списке.
• Получить остальную часть списка, за исключением максимума.
• Сортируйте оставшуюся часть списка и поместите максимум в начало списка.

Это не очень быстрый способ сортировки, но он должен работать. Следующим шагом в вашем коде будет написание функции для получения остальной части списка, за исключением максимума (позаботьтесь о правильной обработке, если в списке есть дубликаты).

После того, как вы это написали, вы сможете написать код Схемы, более или менее похожий на приведенный выше план.

Answer 2

Это алгоритм сортировки слиянием в Common lisp. Это примерно близко к реализации того же вида в схеме.

(defun merge-sort( input )
  (labels ((right-half ( input )
             (last input (ceiling (/ (length input) 2))))
           (left-half ( input )
             (ldiff input (right-half input ))))
    (if (or (null input) (null (cdr input))) 
        input 
        (merge 'list (merge-sort (left-half input)) (merge-sort (right-half input)) #'<))))

Answer 3

Вы не указали реализацию, которую используете. Но он может реализовать либо r6rs list-sort , либо srfi-95 sort , либо любую другую встроенную сортировку. Ознакомьтесь с документацией вашей реализации.

Answer 4

Вам нужно решить, что использовать для сортировки списка. Недавно я возился со схемой, пробираясь через SICP и серию «Schemer», и мне было довольно легко реализовать в схеме сортировку по пузырькам, сортировку слиянием и быструю сортировку.