離散システム特論整列(sorting)アルゴリズム２参考文献 1. 大森克史・木村春彦・広瀬貞樹著「アルゴリズムの基礎」共立出版(1997) 2. 渡邊敏正著「データ構造と基本アルゴリズム」共立出版(2000) 整列とは  全順序集合Sが与えられたとき，Sのすべての要素をその全順序に従って並べ替えること．  簡単のため，ｎ個の整数の集合をSとし，通常の数字の大小関係で小さい数から大きい数へ並べ替えるとする（昇順ソート ascending sort)．ソーティングアルゴリズム         選択法 (selection sort) バブルソート (bubble sort) 挿入法 (insertion sort) クイックソート (quick sort) ヒープソート (heap sort) マージソート (merge sort) バケットソート (bucket sort) 基数ソート(radix sort) O(n2) O(n log n) ソーティングアルゴリズムの限界マージソート（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) より T(n) 2T(n/2)+n  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 abc bca acb cba cab yes yes no no a<c a<c bca bac abc cab cba acb yes b<c no yes b<c no bca cba abc acb ソートされた状態決定木の深さの下限葉はすべてのソートされた状態に対応．．．総数は n! 最悪の場合（運の悪い問題例）では，決定木の深さ分の比較が必要． abc, acb, bac, bca, cab, cba 葉の数がn!の決定木（２分木）の深さは最低でもどのくらいか？ yes yes abc acb cab a<c no cab abc acb yes b<c no abc acb a<b no bac bca cba yes a<c bac no bca cba yes b<c no bca cba 決定木の深さの下限（２） • 深さ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 基準値（４，１０，５，２，１，７，９，３，８，６） right left 基準値（４，１０，５，２，１，７，９，３，８，６） left right 基準値（４，3，５，２，１，７，９，10，８，６） left right 基準値クイックソートの例(2) （４，3，５，２，１，７，９，10，８，６）基準値 right left （４，3，５，２，１，6，９，10，８，7） (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) が等確率におこるとすると， 1 n1 T(n)   T(i)  T(n 1 i)  n 1 n i 0 クイックソートの平均計算量(2) n1 1 T(n)   T(i)  T(n 1 i)  n 1 n i 0 s(n) S(n 1) 2   n 1 n n 1 S(n  2) 2 2    n 1 n n 1 S(1) 2 2 ......    2 3 n 1 1 1 1  2(1     2) 2 3 n 1 2 n1   T(i)  n 1 n i 0 n1 n(T(n)  2) n(n  1)  2 (T(i)  2) i 0 S(n)=T(n)-2とおくと， nS(n) = n(n+1)+2(S(0)+S(1)+…+S(n-1)) ( S(1)  T(1)  2  2) (n-1)S(n-1) = (n-1)n +2(S(0)+S(1)+…+S(n-2)) 引き算すると， nS(n) = (n+1)S(n-1)+2n よって，  S(n) 2(n+1)Hn+1 =O(nlog n) レポート課題 ① ② ③ 講義で取り上げなかったソーティングアルゴリズムについて調べ，計算量の算定もせよ．講義で扱ったソーティングアルゴリズムを３つ選び，それを自分でプログラムし，様々な入力に対する実行時間の比較をせよ．２００４年２月期大学院入試問題計算機科学II（整列の問題）を解け． http://www.sk.tsukuba.ac.jp/SSE/admission/p astexams.htmlより入手