2

スキームでマージソートを実装していますが、マージとスプリットの 2 つのヘルパー メソッドを定義する必要があります。

Merge は 2 つのリスト (既に昇順になっています) を取り、それらをマージします。私は次のようにこれを行いました：

(define merge 
   (lambda (list1 list2)
       (if (null? list1)
          list2
             (if (null? list2)
                list1
                   (if (< (car list1) (car list2))
                      (cons (car list1) (merge (cdr list1) list2))
                      (cons (car list2) (merge (cdr list2) list1)))))))

ただし、分割方法には困惑しています。2 つの別々の方法 (「奇数」と「偶数」) でこれを実現する例を見つけましたが、これらを「分割」と呼ばれる 1 つの方法に結合する方法があるかどうか疑問に思っていました。

ここにある例:スキーム内のマージソート

私は明らかにスキームにまったく慣れていません。これを行う方法を理解するのを手伝ってくれる人はいますか?

4

1 に答える 1

3

splitの一部として使用するのに適した単純な実装は次のmergesortとおりです。

(define (split lst)
  (let ((half (quotient (length lst) 2)))
    (list (take lst half)
          (drop lst half))))

入力リストを 2 つに分割し、それらをリストのリストとして返します。最初のリストは入力リストの前半に対応し、2 番目のリストは入力リストの後半に対応します。

質問で要求されている別の代替手段は、次のようにリストを奇数/偶数要素に分割することです。

(define (split lst)
  (list (filter odd? lst)
        (filter even? lst)))

さらに別の方法として、 を使用partitionすると、入力リストを 1 回のパスで分割できます。

(define (split lst)
  (let-values (((odds evens) (partition odd? lst)))
    (list odds
          evens)))

最後の 2 つの選択肢は、入力リストに整数のみが含まれる場合にのみ役立つことに注意してください。独自の の実装で他のデータ型のリストをソートするにはmergesort、私の最初のバージョンの を使用することをお勧めしますsplit。

于 2012-11-13T01:08:07.670 に答える