2

私はSchemeでマージソートを書いていますが、なぜこれがうまくいかないのか不思議です...

これは私が動作すると期待する実装ですが、動作しません:

(define (mergesort op l)
  (cond ((null? l) l)
      ((null? (cdr l)) l)
      (else (merge op (car l)
                      (mergesort op (cdr l))))
  )
)

そして、これが「適切な」実装です。

(define (mergesort op l)
  (cond ((null? l) l)
      ((null? (cdr l)) l)
      (else (merge op (cons (car l) (list))
                      (mergesort op (cdr l))))
  )
)

再帰とマージしようとする前に、なぜ (cons (car l) (list)) しなければならないのですか?

4

2 に答える 2

4

これに注意してください：

(cons (car l) (list))

...これと同等です：

(list (car l))

つまり、プロシージャの 2 番目のパラメーターとして、要素だけでなく、単一の要素を持つリストを渡す必要があります。merge

于 2013-02-01T22:56:06.220 に答える
2

Oscar の言うことはまったく正しいのですが、これについて見落とされていることが 1 つあります。

これはマージソートではありません。mergesort の定義は? リストを取得し、それを半分に分割し、ソートされた各リストをソートしてから、それらをマージします。

半分に分割しているわけではありません。あなたは1つと残りの部分に分かれています。次に、残りを並べ替えて、単一の要素をリストにマージします。ただし、単一の要素をリストにマージすることは、要素をリストに挿入することと考えることができます。

あ、手がかりがある！挿入 sortを書きました。どちらでも構いません。できます。それははるかに効率が悪いだけです。

したがって、マージソートと挿入ソートの違いは、リストを分割するのに間違った場所を選択することです。

于 2013-02-01T23:36:01.847 に答える