0

clispで挿入ソートとマージソートを書きたいです。入力は数値のフラットなリストになります。これら 2 つの並べ替えを再帰的に (できればラムダを使用せずに) どのように記述しますか? 挿入ソートについては、リストと整数 (目的の要素の現在のインデックスを意味する) を引数として受け取る関数を作成し、setf と nth を使用してリストを操作することを考えていました。その内部には別の再帰関数もあるはずですが、... 保存する関数や変数が多すぎて混乱します。

マージソートについては、まったくわかりません。

4

2 に答える 2

1

マージソートは当然再帰的です (分割統治の問題と同様)

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

彼らが引用した挿入ソートの実装は、一種の反機能的です

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

しかし、ループは簡単に末尾再帰に変えることができます。

于 2012-03-10T23:58:47.290 に答える
0

古い質問だと思いますが、Common Lisp スタイルで Mergesort の再帰的な実装を作成する方法にも興味があったので、次のように書きました。

(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)))

どんな提案でも大歓迎です！

于 2016-07-13T11:34:29.157 に答える