離散システム特論 整列(sorting)アルゴリズム　２

参考文献 大森克史・木村春彦・広瀬貞樹 著 「アルゴリズムの基礎」 共立出版(1997) 大森克史・木村春彦・広瀬貞樹　著　「アルゴリズムの基礎」　共立出版(1997) 渡邊敏正　著　「データ構造と基本アルゴリズム」　共立出版(2000)

整列とは 全順序集合Sが与えられたとき，Sのすべての要素をその全順序に従って並べ替えること． 簡単のため，ｎ個の整数の集合をSとし，通常の数字の大小関係で小さい数から大きい数へ並べ替えるとする（昇順ソート　ascending sort)．

ソーティングアルゴリズム 選択法 (selection sort) バブルソート (bubble sort) 挿入法 (insertion sort) クイックソート (quick sort) O(n2) ヒープソート　(heap sort) マージソート (merge sort) O(n log n) ソーティングアルゴリズムの限界 バケットソート　(bucket sort) 基数ソート(radix sort)

マージソート （merge sort) 分割統治法 入力を２つに分割して，分割した各々を整列した後に，それらを統合する．分割した部分の整列にも再びマージソートを用いる．つまり，再帰的にソートが行われる． 分割統治法 divide-and -conquer method

マージソートの擬似コード s=1, t=n; mergesort(s, t){ // sからtの要素をソート if (s ≠ t){ 　　 A1 = mergesort(s, (s+t)/2); 　 //sから半分までをソートしてA1にしまう A2 = mergesort( (s+t)/2+1, t);　 //半分からtまでをソートしてA2にしまう． 　　 merge (A1, A2);　//A1とA2をあわせる }

マージソートの例 （４，１０，５，２，１，７，９，３，８，６） 分割 （４，１０，５，２，１）（７，９，３，８，６） 分割　（４，１０，５，２，１）（７，９，３，８，６） 分割　（（４，１０，５）（２，１））（（７，９，３）（８，６）） 分割　（（（４，１０）（５））（（２）（１）））（（（７，９）（３））（（８）（６））） 分割（（（（４）（１０））（５））（（２）（１）））（（（（７）（９））（３））（（８）（６））） 統治（（（４，１０）（５））（（２）（１）））（（（７，９）（３））（（８）（６））） 統治（（４，５，１０）（１，２））（（３，７，９）（６，８）） 統治（１，２，４，５，１０）（３，６，７，８，９）

マージソートの例（統治） （１，２，４，５，１０）　　　　（３，６，７，８，９） １ ２ ３ ４ ５ ６ ７ ８ ９ １０

マージソートの計算量 Ｔ（ｎ）：マージソートの計算量 統治 T(n) 2T(n/2)+n (n2) 1 (n=1) より  2{2T(n/22)+n/2}+n = 22T(n/22) + 2n 22 {2T(n/23)+n/22} +2n = 23T(n/23) + 3n …  2kT(n/2k) + kn (k = log n) よって，T(n) = n+n log n =O(n log n)

ソーティングアルゴリズムの下限 ２つの要素の大小比較が基本操作のアルゴリズム → アルゴリズムの判断の分岐数は２ 　→　アルゴリズムの判断の分岐数は２ 計算のいかなる進行もまとめて，決定木(decision tree）で表せる． 各頂点は，それまでの計算によって獲得された状態． ２要素の比較がその状態から出る２本の枝 葉がソートされた状態

２要素の比較はどれでもよい．名付けをかえればよいので． 決定木 {a, b, c}のソート ２要素の比較はどれでもよい．名付けをかえればよいので． abc, acb, bac, bca, cab, cba その時点で考え得る状態 a<b no yes bac bca cba abc acb cab yes ソートされた状態 yes no no a<c a<c bac bca cba abc acb cab yes yes no no b<c b<c bca cba abc acb

決定木の深さの下限 葉はすべてのソートされた状態に対応 ．．．総数は n! 最悪の場合（運の悪い問題例）では，決定木の深さ分の比較が必要． abc, acb, bac, bca, cab, cba abc acb cab bac bca cba yes no a<b a<c b<c 葉の数がn!の決定木（２分木）の深さは最低でもどのくらいか？

決定木の深さの下限（２） 深さdの２分木の葉の数は，高々2d 2d  n! を満たす最小のdをみつければよい． Ｓｔｉｒｌｉｎｇの公式： N! ≒　√2πn nn e-n より，d ≒n log n ソーティングアルゴリズムはO(nlog n)より早くならない．（ヒープソートは最適．） 一般的にアルゴリズムの下限を示すのは大変． バケットソート，基数ソートは比較以上の情報がある．

クイックソート(quick sort) １つの要素aを基準とし，aよりも小さい要素をaの左にaよりも大きい要素をaの右に分割する．分割した部分の整列も再帰的にソートを行う． マージソートと同じで分割統治法．ただし， 分割は等分ではない 統治の操作は必要ない

基準値による分割の擬似コード a1からan-1をanを基準値にして分割．a0は十分小さな値が入っていると仮定 left :=1, right:=n-1; while(left<right) { while (aright > an){ right:=right-1; } while (aleft < an){ left:=left+1; swap (aleft, aright); swap (aleft, an);

クイックソートの例(1) （４，１０，５，２，１，７，９，３，８，６） 基準値 right left （４，3，５，２，１，７，９，10，８，６） 基準値 left right

クイックソートの例(2) （４，3，５，２，１，6，９，10，８，7） （４，3，５，２，１，７，９，10，８，６） 基準値 right left (4, 3, 5, 2, 1) (9, 10, 8, 7) あとはよろしく

クイックソートの計算量 基準値をソートする部分の最小値が常に選ばれてしまうと，選択法と変わらない． ↓ 最悪時間計算量はO(n2) 平均時間計算量はO(n log n)

クイックソートの平均時間計算量 Ｔ（ｎ）：ｎ個のデータをクイックソートする平均時間 T(n) = T(m1)+T(m2)+n-1, ただし，m1+m2=n-1 (m1, m2):(0, n-1), (1, n-2), …, (n-1, 0) が等確率におこるとすると，

クイックソートの平均計算量(2) S(n)=T(n)-2とおくと， nS(n) = n(n+1)+2(S(0)+S(1)+…+S(n-1)) よって， S(n) 2(n+1)Hn+1 =O(nlog n) 引き算すると， nS(n) = (n+1)S(n-1)+2n

レポート課題 講義で取り上げなかったソーティングアルゴリズムについて調べ，計算量の算定もせよ． 講義で扱ったソーティングアルゴリズムを３つ選び，それを自分でプログラムし，様々な入力に対する実行時間の比較をせよ． ２００４年２月期大学院入試問題計算機科学II（整列の問題）を解け．http://www.sk.tsukuba.ac.jp/SSE/admission/pastexams.htmlより入手