일반적인 Lisp 병합 정렬 내역

Question

간단히 말하자면 알고리즘 클래스가 너무 쉽기 때문에 몇 가지 이유 때문에 Common 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 

참고 :이 내가 작성한 코드, 인터넷으로 확보하지 ... 당신은 아마 당신은 동적 범위에 물린있어하지만 하하

Answer 1

을 알 수 있습니다 변수. 처음 SETF를 호출하여 a, b를 설정하면 전역 적으로 동적으로 범위가 지정된 변수가 암시 적으로 만들어집니다. 대신 LET을 사용하여 선언하십시오. LET을 사용하면 PROGN과 같이 실행할 표현식 목록을 포함 할 수 있으므로 2 PROGN을 LET으로 변경하여이 문제를 해결할 수 있다는 힌트를 얻을 수 있습니다. 당신이 풀려나 기 위해 이것 이상을 필요로하는지 알려주세요.