Сортировка в Clisp

Question

Я хочу написать сортировку вставки и сортировку слиянием в clisp.На входе будет простой список чисел.Как можно написать эти 2 вида рекурсивно (желательно без использования лямбд)?Для сортировки вставкой я думал о создании функции, которая принимает список и целое число (которое должно быть текущим индексом интересующего элемента) в качестве аргументов, и используя setf и nth для манипулирования списком.Я знаю, что внутри него также должна быть другая рекурсивная функция, но, как ... Я просто запутался с таким количеством функций и переменных для хранения и прочее.

Для сортировки слиянием я абсолютно не представляю.

Answer 1

Сортировка слиянием естественно рекурсивна (как любая проблема «разделяй и властвуй»)

http://en.literateprograms.org/Merge_sort_(Lisp)

Упомянутая реализация сортировки вставками является антифункциональной

http://en.literateprograms.org/Insertion_sort_(Lisp)

Но вместо этого петли можно легко превратить в хвостовую рекурсию.

Answer 2

Я вижу, что это старый вопрос, но я был также взволнован, как написать рекурсивную реализацию Mergesort в стиле Common Lisp, поэтому я написал это так:

(defun mergesort (lo hi)
  (let ((mid 0)
  (items 0))

  ;; initializations
  (setq items (- hi lo))
  (multiple-value-bind (intreg rest)
  (floor (/ (+ hi (1+ lo)) 2))
    (setq mid intreg))

  ;; recursive call if more than 1 item
  (cond ((> items 1)
    (mergesort lo mid)
    (mergesort mid hi)))

  ;; merge step
  (let ((temp (sort-range *unsorted-list* lo mid hi)))
  (do ((x lo (1+ x))
   (tx 0 (1+ tx)))
  ((= x hi))
(setf (nth x *unsorted-list*) (nth tx temp))))
))

;; collect and sort range between low and high
(defun sort-range (LIST lo mid hi)
  (labels ((collect-range (i1 i2)
     (if (and (< i1 mid) (< i2 hi))
     (let ((lv (nth i1 LIST))
           (rv (nth i2 LIST)))

       (if(and (< lv rv) (< i1 mid))
          (cons lv (collect-range (1+ i1) i2))
          (if(<= i2 hi)
         (cons rv (collect-range i1 (1+ i2))))
          ))
     (if (< i1 mid)
         (cons (nth i1 LIST) (collect-range (1+ i1) i2))
         (if(< i2 hi)
        (cons (nth i2 LIST) (collect-range i1 (1+ i2)))))
     )))
(collect-range lo mid)))

Любые предложения приветствуются!