一般的なLisp Merge Sortが破損しました
-
14-11-2019 - |
質問
私は共通のLispの私のアルゴリズムクラスのすべての割り当てをすることを私自身に挑戦しました。私はLispを学び、私は障害物を襲いました。
代入は、任意のサブセット長(TIMSORT)に到達したときに挿入に変換するマージソートを作成することです。挿入部は完全に機能しますが、マージの分割部分はプログラムが2回分割されなければならない場合にのみ機能します。私はそれが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 に言うことができます
解決
動的に箱詰まにされた変数に噛まれています。setfを最初に呼び出して、Bを設定します.bは、グローバル、動的にスコープされた変数を暗黙的に作成します。代わりにそれらを宣言するために使用してください。Prognのように、実行する式のリストを含めることを可能にしましょう。あなたが不安定になるためにこれ以上のものを必要とするかどうか私に知らせてください。
所属していません StackOverflow