Schemeでマージソート

やってみた。

(define merge-sort
  (lambda (lis)
    (if (= (length lis) 1)
      lis
      (let* ((n (div (length lis) 2))
             (left (take lis n))
             (right (drop lis n)))
        (merge (merge-sort left) (merge-sort right))))))

(define merge
  (lambda (lis1 lis2)
    (let loop ((l1 lis1) (l2 lis2) (l0 '()))
      (cond ((and (null? l1) (null? l2)) (reverse l0))
            ((null? l1) (loop l1 (cdr l2) (cons (car l2) l0)))
            ((null? l2) (loop (cdr l1) l2 (cons (car l1) l0)))
            ((< (car l1) (car l2)) (loop (cdr l1) l2 (cons (car l1) l0)))
            (else (loop l1 (cdr l2) (cons (car l2) l0)))))))

(print (merge-sort '(5 1 7 6 8 2 9 3 4)))

実行結果:

^o^ > gosh merge-sort.scm
(1 2 3 4 5 6 7 8 9)
カテゴリー: algorithm, Scheme パーマリンク

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください