Общий сортировка слияния Lisp

Question

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

Назначение состоит в том, чтобы создать сорт слияния, который преобразует в вставку, когда вы попадаете в произвольную длину подмножества (Timsort).Раздел вставки отлично работает, но раскол только слияния работает только тогда, когда программа должна разделить дважды.Я знаю, что это связано с дорогими списками работы в Lisp, я просто новичок, чтобы точно определить проблему.

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

Я не здесь умоляю конкретных ответов или для кого-то, чтобы написать свой код.Может быть, объяснение или точка в правильном направлении очень помогут!

Мой код:

;; Insertion sort method call (returns sorted list)
(defun insert-sort (lst) ... )

;; Merge sort method call
(defun merge-sort (lst)
  (print 'Merge)
  (print lst)
  (if (< (length lst) 7) ; Check to see if list is small enough to insert sort
      (insert-sort lst) ; Do so
      (progn ; else
        (setf b (merge-split lst)) ; Split the list, store into b
        (setf (car b) (merge-sort (car b))) ; Merge sort on first half
        ;; --- I think it's happening here ---
        (setf (cdr b) (merge-sort (cdr b))) ; Merge sort on second half
        (merge 'list (car b) (cdr b) #'<)))) ; Merge the two lists together (using API)

;; Split a list into two parts
(defun merge-split (lst)
   (progn
     (setf b lst) ; Set b to first index
     (setf a (cdr lst)) ; Set a to the rest of the list
     (loop while a do ; Loop while a != null
           (setf a (cdr a)) ; Make a equal next list node
           (if a ; If it still exists
               (progn
                 (setf a (cdr a)) ; Inc a again
                 (setf b (cdr b))))) ; Also inc b (b should always be half of a)
     (setf a (cdr b)) ; Set a to the list after b
     (setf (cdr b) NIL) ; Delete link after b
     (cons lst a))) ; Return in a cons

.

Примечание. Это код, который я написал, не выгнал в Интернет ... Вы, вероятно, можете сказать, хотя HAHA

Answer 1

Вы укусили динамически выделенные переменными.Первый раз, когда вы вызываете SetF, чтобы установить A, B, вы неявно создаете глобальные, динамически определенные переменные.Использовать пусть вместо этого объявить их.Пусть позволяет вам включить список выражений для выполнения, так же, как Prognog, поэтому мой намек в том, что вы можете исправить это, изменив 2 Prognss в позволяет.Дайте мне знать, если вам нужно больше, чем это отклеиться.