0

私はSchemeでマージソートを書いています。マージソート定義、リストを分割するスプリッター、およびリストをマージするマージがあります。

(define mymergesort
  (lambda (alist)
    (if (null? (cdr alist)) alist
        (let ((splits (splitter alist)))
          (merge (mymergesort (car splits)) (mymergesort (cadr splits)))))))

(define splitter
  (λ (alist) (splitter-helper alist () ())))

(define splitter-helper
  (λ (alist list_a list_b)
    (cond ((null? alist) (cons (reverse list_a) (cons list_b ())))
          ((null? (cdr alist)) (cons (reverse (cons (car alist) list_a)) (cons list_b ())))
           (else (splitter-helper (reverse (cdr (reverse (cdr alist)))) (cons (car alist) list_a) (cons (car (reverse (cdr alist))) list_b))))))

(define merge
  (λ (list_a list_b)
    (cond ((null? list_a) list_b)
          ((null? list_b) list_a)
          ((<= (car list_a) (car list_b)) (cons (car list_a) (merge (cdr list_a) list_b)))
          ((<= (car list_b) (car list_a)) (cons (car list_b) (merge list_a (cdr list_b)))))))

この実装は、数値のリストをソートするのにうまく機能するようです。しかし、混合要素のリストをソートできるようにしたいと考えています。

例: '(I can "go" 4 "about" 123 sodas k?)

提案/解決策はありますか？また、再帰的なソリューションを「ごまかす」長さなどのほとんどのプロシージャの使用を避けようとしています。

4

1 に答える 1

1

これらのアイテムをランク付けする「ヒューリスティック」が必要になります。たとえば、「go」は「about」の前に来ますか？4はどうですか？したがって、並べ替えたい要素が別の要素に対して「<=」であるかどうかを判断する関数を作成できます。また、

(<= (car list_a) (car list_b))そして、(<= (car list_b) (car list_a))一種の冗長です。a が <= b でない場合、a > b であることがわかります。

于 2013-02-08T11:13:28.277 に答える