私は昨年の秋頃の情報処理学会の雑誌に, 計算機科学はもう終ったという 話を書いて物議を醸したが, その余韻も収まらぬうちに, 計算機科学者の 大物のTony死去の通知を受け取った.
Tony Hoareといえば, クィックソートを提案したことで知られる. クィッ クソートは計算機科学の主要な話題の1つであったが, もう大学の講義で 語られることはないかも知れない. 今回のブログは,クィックソートをお さらいしよう.
クィックソートを一言でいえば, ある数列をいきなりソートするのではな く, 数列をその中央値(アルゴリズムではその値をピボットという)より小 さいものの列と大きいものの列に2分割し, それぞれをソートしてからそ の結果を連結するものである. 厳密な中央値は, ソートしてみないと分ら ないから, この説明は矛盾しているが, 実際には適当な要素を中央値であ ることを祈って使う.
長さがnの数列をソートする手間がnの二乗だとすると, 2分割した数列の ソートの手間は, 片側で4分のn二乗になり, 両方では2分のn二乗になって 効率的になるというのが趣旨である.
ソートすべき数列がピボットで大小に分割され, そのそれぞれをソートす ることで進行する様子を示したのが次の図である. 一番上は最初のソート される数列で, 左端の6をピボットにして分割したのが2段目である. ピボッ トより小さいものが左に集まり, 大きいのが右に集る. このそれぞれはも うピボットを越えて反対側にいくことはない. ピボットになった数も最 終の位置に収まった. 大小それぞれの部分列をさらに再帰的にソートする のだが, 再帰アルゴリズムでは停止条件が必要で, 今の場合はもうソート する必要のない, 長さが1以下の数列になったときである.
この方針だと, ソートすべき数列lsについて, ピボットは(car ls)で, 残 り(cdr ls)をピボットより小さい(等しいのも)のグループと, より大きい のグループにする. その安易は方法は, 例えばschemeではfilter関数を使 い,
(let ((p (car ls)) (qs (cdr ls))) (filter (lambda (a) (<= a p))) qs) (filter (lambda (a) (< p a))) qs))とすればよいが, こんなところでfilterのような大型命令を使うのには, ある種のうしろめたさが残る. 大型命令を使うならSchemeでは最初から
(sort '(3 4 1 2 5 0) <)と書けばよい.
ということで, 分割のプログラム part を書いてみる.
(define (part ls)
(define (swap i j) (let ((t (list-ref ls i)))
(list-set! ls i (list-ref ls j))
(list-set! ls j t)))
(let ((p (car ls)) (l 1) (r (- (length ls) 1)))
(while (<= l r)
(while (and (<= l r) (<= (list-ref ls l) p))
(set! l (+ l 1)))
(while (and (<= l r) (> (list-ref ls r) p))
(set! r (- r 1)))
(if (< l r) (swap l r)))
(swap 0 r)
(list (take r ls) (list-ref ls r)
(drop (+ r 1) ls))))
いくつかの数列でやってみる. 上からランダムな数列, ピボットが最小値,
ピボットが最大値, 数列の長さが1, 数列の長さが2の例である.
(part '(3 4 1 2 5 0)) => ((2 0 1) 3 (5 4)) (part '(0 1 2 3 4 5)) => (() 0 (1 2 3 4 5)) (part '(5 4 3 2 1 0)) => ((0 4 3 2 1) 5 ()) (part '(0)) => (() 0 ()) (part '(0 1)) => (() 0 (1)) (part '(1 0)) => ((0) 1 ())lsは分割する数列. (swap i j)はそのi番目要素とj番目要素を交換するルー チン.
letに入って, pはピボット. lとrは数列を探索為るポインタの初期化. l はピボットを除いた数列の左端から右方へ, rを超えない範囲でピボット に等しいかピボットより大きい数を探す. rは反対に数列の右端から左方 へ, lを超えない範囲でピボットより小さい数を探す.
プログラムの結果は, 小さいか等しいもののリスト, ピボット, 大きいも ののリストの3つ組で示す.
この夫々について, lとrの動きを示したのが次の図である.
(define (quicksort ls)
(define (qsort ls)
(define (swap i j) (let ((t (list-ref ls i)))
(list-set! ls i (list-ref ls j))
(list-set! ls j t)))
(if (<= (length ls) 1) ls
(let ((p (car ls)) (l 1)
(r (- (length ls) 1)))
(while (<= l r)
(while (and (<= l r) (<=(list-ref ls l) p))
(set! l (+ l 1)))
(while (and (<= l r) (> (list-ref ls r) p))
(set! r (- r 1)))
(if (< l r) (swap l r)))
(swap 0 r)
(append (qsort (take r ls)) (list p)
(qsort (drop (+ r 1) ls))))))
(qsort ls))
アルゴリズムの解説を見ると, ピボットを中央値に近付けるべく, 数列か
ら3個所の値を取ってその中央値を使うとか, ソートする数列の長さがあ
る程度短くなると, 通常のソートに切り換えるとか書いてあるが, プログ
ラムを美しくするという立場からは,そういう些細なことは採用したくな
い.ところで, 上のquicksortでは, qsortがソートすべき数列の部分列lsを受 け取り,その部分をソートして返す構造である. これに対し, quicksortが 受け取った数列全体lsに対し, leftを左端, rightを右端とするその一部 に直接交換を繰り返してソートする方式も考えられる. 下のプログラムは, 下請けのqsortは, その左右の限界を受け取り, 大域的な数列lsの数を交 換するようになっている.
ソートする数列の数が, 直接交換されて揃うのを想像するには, この方が よいように思うがどうだろうか.
(define (quicksort ls)
(define (qsort left right)
(define (swap i j) (let ((t (list-ref ls i)))
(list-set! ls i (list-ref ls j))
(list-set! ls j t)))
(if (> (- right left) 0)
(let ((p (list-ref ls left)) (l (+ left 1))
(r right))
(while (<= l r)
(while (and (<= l r) (<= (list-ref ls l) p))
(set! l (+ l 1)))
(while (and (<= l r) (> (list-ref ls r) p))
(set! r (- r 1)))
(if (< l r) (swap l r)))
(swap left r)
(qsort left (- r 1)) (qsort (+ r 1) right))))
(qsort 0 (- (length ls) 1)) ls)
この2通りのquicksortの方式についての私のイメージはこうである. 始め
のqsort ls方は, ある家庭で洗濯物を袋に入れて洗濯屋に依頼する. その
洗濯屋は洗濯物をこれこれこれとそれそれそれに分けて別々の袋に入れ,
下請けの洗濯屋に洗濯を依頼する. やがて両方の下請けから洗濯が出来上っ
て来ると, それらを合わせて依頼した家庭に屆ける.それに対して, qsort left rightの方は, 棚の上に多くの盆栽を並べて楽 しんでいる御隠居が, 盆栽の手入れを盆栽屋に依頼する. 盆栽屋はこれこ れこれの盆栽とそれそれそれの盆栽に分類し, それぞれを下請けの盆栽屋 に手入れを依頼する. やがて両方の下請けの盆栽屋から手入れが終わった と報告を受けると, 始めの盆栽屋は御隠居に手入れは終りましたと報告す る.
書いてみると, あまり違いがないような気もするが, 読まれた方の印象は どうであろうか.
