第11回 整列 ～ バケットソート，基数ソート，ヒープソート～ データ構造とアルゴリズム 第11回 整列 ～ バケットソート，基数ソート，ヒープソート～

前回の課題(1) 降順！ 正解は75.3% 下記の疑似コードにしたがってソートする時，外側のforループの各 i での配列aの内容を記せ． 配列の要素数nは6とし，配列aの初期値は先頭から順に{ 8, 4, 3, 9, 1, 5 }であるものとする． void sort(int a[], int n) { int i, j; for (i = 0; i < n - 1; i++) for (j = n - 1; j > i; j--) if(a[j] > a[j-1]) a[j]とa[j-1]を交換; } 降順！

解答(1) a[0][1][2][3][4][5] 初期値 8, 4, 3, 9, 1, 5 i=0の後 9, 8, 4, 3, 5, 1 初期値 8, 4, 3, 9, 1, 5 i=0の後 9, 8, 4, 3, 5, 1 i=1の後 9, 8, 5, 4, 3, 1 i=2の後 9, 8, 5, 4, 3, 1 i=3の後 9, 8, 5, 4, 3, 1 i=4の後 9, 8, 5, 4, 3, 1 降順

本日の内容 比較によらないソート バケットソート 基数ソート ヒープソート

バケットソート (bucket sort) 別名 ビンソート(bin sort) ともいう 計算量 O (n) バケットソートを適用できる条件： n個の要素は整数で0以上m-１以下の値をとるとする。 バケット 1 2 m-1

バケットソートの原理　　　 １．値kの要素を入れる箱(バケットB[k]、ただし、kは０≦k≦m-1)を準備し、各要素A[i]をB[A[i]]に入れる。 　　　　　　　 B[A[i]]　= A[i]; ２．バケットをB[0], B[1], …,B[m-1]の順に連結する。 A = {0, m-1, … , 2} m-1 1 B[0] B[1] B[2] B[m-1]

バケットソートの概念図 バケットB 配列 A [0] 1 [0] A[2] [1] 4 [1] A[0] [2] [2] A[4] [3] バケットソートの概念図　　 バケットB 配列 A [0] 1 [0] A[2] 最後にデータをバケット から順に取り出し， 配列に戻して整列終了 キーに 重複がない場合 [1] 4 [1] A[0] [2] [2] A[4] [3] 6 [3] [4] 2 [4] A[1] [5] 空のバケット [6] A[3]

キーに重複がある場合 バケットB 配列 A [0] A[2] [1] A[8] A[6] A[4] A[0] [2] A[9] [3] なし キーに重複がある場合　　 i番目のバケットに要素が 何個入るか分からない ⇒連結リストで表現 バケットB 配列 A [1] [2] [3] [4] [5] [6] [7] [8] [9] [0] 1 6 5 4 2 [0] A[2] [1] A[8] A[6] A[4] A[0] [2] A[9] [3] なし [4] A[7] [5] A[5] [6] A[3] A[1]

バケットソートの実現（手順1） バケットB への格納 配列 A バケットB [1] [2] [3] [4] [5] [6] [7] [8] バケットソートの実現（手順1）　　 バケットB　への格納 配列 A バケットB [1] [2] [3] [4] [5] [6] [7] [8] [9] [0] 1 6 5 4 2 [0] A[2] [1] A[8] A[6] A[4] A[0] [2] A[9] 空のバケット [3] [4] A[7] [5] A[5] [6] A[3] A[1]

この例では，先頭に要素を追加したが，末尾に追加すれば，順序関係が維持される⇒安定 バケットソートの実現（手順2）　 バケットB[i]とB[i+1]の要素を連結 (CONCATENATE)する。 B [0] A[2] [1] A[8] A[6] A[4] A[0] [2] A[9] この例では，先頭に要素を追加したが，末尾に追加すれば，順序関係が維持される⇒安定 [3] A[7] [4] [5] A[5] [6] A[3] A[1]

バケットソートの特徴 計算量O(n) バケットのためのメモリが必要． （所要メモリ量はデータ数nに比例） バケットソートの特徴　　 計算量O(n) バケットのためのメモリが必要． （所要メモリ量はデータ数nに比例） キーの種類数 m がある程度小さい場合に使用可．種類数mが大きい場合は現実的でない． 例 int型=4バイト(32ビット) –2147483648～2147483647 種類数は約40億種

基数ソート（radix sort） radix : 基数．基礎として用いる数． 10進法の基数は10 （0から9まで） 10進法の基数は10　　　（0から9まで） 16進法の基数は16　　　（0から15（F）まで） 整列対象となるキーを，いくつかのサブキーに分割し，下位から上位の順に，サブキーをもとに安定な整列を行う サブキーの整列には，計算量O(n)の安定なアルゴリズムを使用

基数ソートの例 90 基数個のバケットを用意 基数１０で，３桁に分割した場合 バケット B 配列 A [1] [2] [3] [4] [5] 基数ソートの例　　　　　　 基数個のバケットを用意 各バケットは待ち行列 基数１０で，３桁に分割した場合 バケット B 100 90 230 231 602 362 112 123 454 517 配列 A [1] [2] [3] [4] [5] [6] [7] [8] [9] [0] 128 [10] 100 602 90 362 128 517 123 454 112 230 配列 A [1] [2] [3] [4] [5] [6] [7] [8] [9] [0] 231 [10] [1] [2] [3] [4] [5] [6] [7] [8] [9] [0] 100　90　230 231 602 362 112 123 454 517 128 一の位で バケット ソート 先頭から 連接

基数ソートの例 90 基数個のバケットを用意 基数１０で，３桁に分割した場合 配列 A [1] [2] [3] [4] [5] [6] 基数ソートの例　　　　　　 基数個のバケットを用意 各バケットは待ち行列 基数１０で，３桁に分割した場合 100 90 230 231 602 362 112 123 454 517 配列 A [1] [2] [3] [4] [5] [6] [7] [8] [9] [0] 128 [10] バケット B 100 602 112 517 123 128 230 231 454 362 配列 A [1] [2] [3] [4] [5] [6] [7] [8] [9] [0] 　90 [10] [1] [2] [3] [4] [5] [6] [7] [8] [9] [0] 　　100 602 　 112 517 十の位で バケット ソート 先頭から 連接 123 128 230 231 454 362 90

基数ソートの例 基数個のバケットを用意 基数１０で，３桁に分割した場合 配列 A [1] [2] [3] [4] [5] [6] [7] 基数ソートの例　　　　　　 基数個のバケットを用意 各バケットは待ち行列 基数１０で，３桁に分割した場合 　90 100 112 123 128 230 231 362 454 517 配列 A [1] [2] [3] [4] [5] [6] [7] [8] [9] [0] 602 [10] 100 602 112 517 123 128 230 231 454 362 配列 A [1] [2] [3] [4] [5] [6] [7] [8] [9] [0] 　90 [10] バケット B [1] [2] [3] [4] [5] [6] [7] [8] [9] [0] 　　90 　 100 112 123 128 百の位で バケット ソート 先頭から 連接 230 231 362 454 517 602

基数ソートによる文字列の整列 さとう ささき さわだ k文字の文字列において、i番目の文字をキーとしてバケットソートを適用することで整列する。 ただし、処理は文字列の末尾から先頭の順に行う。 k=3 さとう ささき さわだ ← i

辞書式順序(lexicographical order) 単語 x = a1a2…akと y = b1b2…bkについて考える． あるiに対し、aj=bj j=1,2,…, i-1で、かつai＜biのとき、x＜yと定義する。ただし空文字はどの文字より小さいとする。 例　ab＜ba, 　　abd＜aca, 　　bc　＜bcd 　　あり＜りあ， あおい＜あじあ， まき　＜まきば 空文字

例(k=3) a n d a n d m a p a n d c a t t h e c a t a n y t h e b u g k e 辞書式順序に整列できた （基数 128) 一般的な計算機での文字コードの種類数 [0] [1] [2] [0] [1] [2] [0] [1] [2] [0] [1] [2] a n d a n d m a p a n d c a t t h e c a t a n y t h e b u g k e y b u g p u t d i g t h e c a t a n y m a p d i g d i g k e y c a t a n d f o x f o x p u t a n y k e y m a p f o x f o x m a p b u g a n y b u g p u t d i g k e y p u t t h e

実装例 基数ソートを実装する際のバケットのデータ構造の例 基数４の場合 (4進数 13, 12, 11, 22, 23を 　基数４の場合 (4進数　13, 　12, 　11,　 22, 　23を バケットに入れた場合) 13 [0] [1] [2] [3] 12 22 11 23 B バケットごとに，先頭へのポインタと 末尾へのポインタを用意 末尾に追加

基数ソートの特徴 分割数 k とすると，ソートの計算量O(k n) kがデータ数 n より十分小さい場合O(n) 基数ソートの特徴　　 分割数 k とすると，ソートの計算量O(k n) kがデータ数 n より十分小さい場合O(n) バケットのためのメモリが必要． （所要メモリ量はデータ数nに比例） キーのパターンを分割しても，キーの大小関係が維持される場合に利用可（浮動小数点数は×） 整数や短い文字列のソートに利用

問題 次の３文字の系列を基数ソートで辞書式順序に 並べていく過程を示せ。 ( J O Y ), ( R E D ), ( R U N ), ( M I D ) １回目 ２回目 ３回目

解答 ( J O Y ), ( R E D ), ( R U N ), ( M I D ) １回目 ２回目 ３回目 ( R E D )

ヒープソート(heap sort)(p.94) 　 ヒープを用いてデータの整列を行うアルゴリズム 計算量　O (n log n) ヒープ : 配列により半順序木を実現したもの 常に子が親より 大きい木の例 常に子が親より 小さい木の例 3 10 5 9 8 9 6 8 9 10 6 3 7 6 10 18 9 4 1 2

ヒープソートの原理 リストＬ ２，９，５，６，… １．ヒープ（半順序木）を作る（優先度つき待ち行列に入れる） ヒープソートの原理 　 １．ヒープ（半順序木）を作る（優先度つき待ち行列に入れる） ２．以下の処理を繰り返して並べかえる ヒープの先頭の要素と末尾の要素を交換 [先頭]～[末尾-１]の部分の半順序を回復させる 優先度つき 待ち行列 リストＬ ２，９，５，６，… ９ ６ ５ ２

半順序木の構成例 　 初期状態 10 6 9 5 15 15 12 3 18 9 8 11 9 20 10 半順序木　3 5 9 6 8 9 10 10 18 9 15 11 15 20 12 3 6 5 15 9 12 18 10 8 11 20 10 5 6 8 9 18 3 15 11 12 20 初期状態 半順序木

半順序木の構成法 部分木の根の要素を適切な位置まで下げる操作を繰り返すことで，半順序木をボトムアップに構築する 10 6 9 5 15 15 半順序木の構成法 　 部分木の根の要素を適切な位置まで下げる操作を繰り返すことで，半順序木をボトムアップに構築する 10 ←　a[0] 要素数 n = 15 赤字は交換が 必要な箇所 6 9 5 15 15 12 ←　a[n/2-1] (=a[6]) 3 18 9 8 11 9 20 10 ←　a[n-1] (=a[14])

半順序木の構成法 　 10 ←　a[0] 6 9 3 8 9 10 5 18 9 15 11 15 20 12

半順序木の構成法 　 10 ←　a[0] 3 9 5 8 9 10 6 18 9 15 11 15 20 12

並べかえ前の状態 10 5 6 8 9 18 3 15 11 12 20 初期状態：ヒープは配列全体を占めている [0] [n-1] a 3 5 9 6 8 9 10 10 18 9 15 11 15 20 12

並べかえの手順(1) 半順序木の根と右端の葉を交換 10 5 6 8 9 18 3 15 11 12 20 10 5 6 8 9 18 12 並べかえの手順(1) 　 半順序木の根と右端の葉を交換 10 5 6 8 9 18 3 15 11 12 20 10 5 6 8 9 18 12 15 11 3 20 [0] [n-1] a 12 5 9 6 8 9 10 10 18 9 15 11 15 20 3

並べかえの手順(2) 残りの部分の半順序の回復 10 5 6 8 9 18 12 15 11 3 20 [0] [n-2] [n-1] a 並べかえの手順(2) 　 この部分の 半順序を 回復させる 残りの部分の半順序の回復 10 5 6 8 9 18 12 15 11 3 20 子が親より小さい間， 2つの子のうち 小さい方の子 と親を交換していく この部分のヒープを再構成 [0] [n-2] [n-1] a 12 5 9 6 8 9 10 10 18 9 15 11 15 20 3 5 6 10 12

並べかえの手順(3) 半順序木の根と右端の葉を交換 12 6 10 8 9 18 5 15 11 3 20 12 6 10 8 9 18 並べかえの手順(3)　　 半順序木の根と右端の葉を交換 12 6 10 8 9 18 5 15 11 3 20 12 6 10 8 9 18 20 15 11 3 5 [0] [n-1] a 5 6 9 10 8 9 10 12 18 9 15 11 15 20 3 20 5

並べかえの手順(4) 残りの部分の半順序の回復 12 6 10 8 9 18 20 15 11 3 5 [0] [n-3] [n-2] この部分のヒープを再構成 [0] [n-3] [n-2] [n-1] a

最終的な状態 　 以上の操作を繰り返す　⇒　降順に並ぶ 10 9 9 9 8 6 5 3

最終的な状態 　 最下段の右端からみると昇順 10 9 9 9 8 6 5 3

昇順に並べるには？ ヒープを構成するときの親子の大小関係を逆転させればよい 3 18 6 15 11 12 5 9 20 8 10 10 5 昇順にしたいときは，子が親より小さい 半順序木を作る 降順にしたいときは，子が親より大きい 半順序木を作る 3 18 6 15 11 12 5 9 20 8 10 10 5 6 8 9 18 3 15 11 12 20

ヒープソートの計算量 swap (a[1], a[i]); O (1) 最小値を取り出す downMin (…); O ( log (i-1) ) 半順序の回復 ヒープの先頭から最小値を除く処理 →　n-1 回繰り返す 合計回数 ＜ (n-1)・log(n-1) ≒ n log n ヒープソート全体で →　常にO (n log n)

(B U T ), ( F A N ), ( A N Y ), ( K I D ) 本日の問題 (問1)次の5個の整数　{4, 7, 5, 6, 7}をバケットソートでバケットB[i]( 0 ≦ i < 10) を用いて整列する手順を図を用いて説明せよ。 (問2)次の３文字の系列を基数ソートで辞書式順序に並べていく過程を示せ。 (B U T ), ( F A N ), ( A N Y ), ( K I D ) １回目 ２回目 ３回目