list - スキームの 2 番目の要素に基づいてペアのリストを並べ替える

Question

各ペアの 2 番目の要素に基づいて、ペアのリストを昇順で並べ替えるコードを作成する方法について、アドバイスをいただけますか? 例はありませんが、これは簡単に想像できます。

Answer 1

マージソートを書いてみましょう。

(define (mgsort ls cmp)
  (cond
    ((or (null? ls) (null? (cdr ls)))
       ls)
    ; right? ... then,
    (else 
      (split ls '() '() cmp))))

リストを扱う最も基本的なツールは構造的再帰です:

(define (split ls a b cmp)
  (cond 
    ((null? ls) 
       (merge (mgsort a cmp) (mgsort b cmp) cmp))
    (else
       (split (cdr ls) b (cons (car ls) a) cmp))))

あとはmerge、「zip 圧縮」のように、ソートされたリストである 2 つの引数をマージする関数を記述するだけなので、結果もソートされたリストになります。

(define (merge a b cmp)
  (cond 
    ((null? a) b)
    ((null? b) ....)
    ((cmp (car a) (car b))   ; right?
       (cons   
          ... ;; what? ... with what??
          (merge (cdr a) ......)))
    (else
       (cons
          ... 
          (merge a ......)))))

テスト:

(mgsort (list 3 1 5 4 6 2 3) <)
;Value 12: (1 2 3 3 4 5 6)

(mgsort (list (cons 3 1) (cons 4 5) (cons 6 2)) (lambda(a b) (< (cdr a) (cdr b))))
;Value 13: ((3 . 1) (6 . 2) (4 . 5))

---

参照。Lisp でアルファベット順に並べられた 2 つの文字列を、効率的なトップダウン マージ関数の再帰を使用してマージする方法 (Common Lisp では名目上の文字列ですが、内部のリストで実際に機能します)、末尾再帰の手作業による実装modulo cons 最適化手法。