11章「ソート」 - 珠玉のプログラミング（Programming Pearls）

珠玉のプログラミングの11章。

11.5.1

n 回見ればよい物ばかりなのでソートしなくても良さそう。

11.5.2

コード参照。

11.5.3

データ数で計測して交わるところを考える。

11.5.4

すべて同じ値の配列の場合。

11.5.5

問題の意味が分からないので略。

11.5.6

コード参照。

11.5.7

略。

11.5.8

略。

11.5.9

分からなかったので答えを見た。これは思いつかないだろう。

11.5.10 - 14

略。

11.scm

;; Programming Pearls Chapter 11
(import (rnrs)
        (mosh)
        (mosh control)
        (srfi :27)
        (srfi :8)
        (only (srfi :1) list-tabulate)
        (mosh test))

(define (random-vector n)
  (random-source-randomize! default-random-source)
  (list->vector (list-tabulate n (lambda x
                                   ((if (= (random-integer 2) 0) + -) (random-integer n))))))

(define (qsort1 v l u)
  (define (swap i j)
    (let1 tmp (vector-ref v i)
      (vector-set! v i (vector-ref v j))
      (vector-set! v j tmp)))
  (if (>= l u)
      v
      (let loop ([i (+ l 1)]
                 [m l])
        (cond
         [(> i u)
          (swap l m)
          (qsort1 v l (- m 1))
          (qsort1 v (+ m 1) u)
          v]
         [else
          (cond
           [(< (vector-ref v i) (vector-ref v l))
            (swap (+ m 1) i)
            (loop (+ i 1) (+ m 1))]
           [else
            (loop (+ i 1) m)])]))))

(define (qsort2 v l u)
  (define (swap i j)
    (let1 tmp (vector-ref v i)
      (vector-set! v i (vector-ref v j))
      (vector-set! v j tmp)))
  (if (>= l u)
      v
      (let loop ([i u]
                 [m (+ u 1)])
        (cond
         [(<= i l)
          (qsort1 v l (- m 1))
          (qsort1 v (+ m 1) u)
          v]
         [else
          (cond
           [(< (vector-ref v i) (vector-ref v l))
            (swap (- m 1) i)
            (loop (- i 1) (- m 1))]
           [else
            (loop (- i 1) m)])]))))

(define (selsort v)
  (define (swap i j)
    (let1 tmp (vector-ref v i)
      (vector-set! v i (vector-ref v j))
      (vector-set! v j tmp)))
  (define (min v start)
    (let loop ([i start]
               [min-val (vector-ref v start)]
               [min-idx start])
      (cond
       [(= i (vector-length v))
        (values min-val min-idx)]
       [else
        (if (< (vector-ref v i) min-val)
            (loop (+ i 1)
                  (vector-ref v i)
                  i)
            (loop (+ i 1) min-val min-idx))])))
  (define (select v i)
    (receive (min-val min-idx) (min v i)
      (swap min-idx i)))
  (do ([i 0 (+ i 1)])
      ((= i (vector-length v)) v)
    (select v i)))

(let1 v (random-vector 100)
  (display (selsort v)))

珠玉のプログラミング—本質を見抜いたアルゴリズムとデータ構造

posted with amazlet at 09.07.11

ジョン ベントリー
ピアソンエデュケーション
売り上げランキング: 5607

Amazon.co.jp で詳細を見る