第11回 整列 ～ シェルソート，クイックソート ～ データ構造とアルゴリズム 第11回 整列 ～ シェルソート，クイックソート ～

問1 解答例1 (抽象的な説明例) 4 7 5 6 B [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 4 問1　解答例1　(抽象的な説明例) 4 7 5 6 A [0] [1] [2] [3] [4] 5個の整数が配列Aに格納 されているものとする バケットBにデータを格納する B [0] [1] [2] [3] [4] A[0] A[2] A[3] A[1] A[4] [5] [6] [7] [8] [9] バケットの先頭から順に 取り出し、配列Aに戻す 4 5 6 7 A’ [0] [1] [2] [3] [4]

問1 解答例2 (ポインタを用いた実装を想定した例) 問1　解答例2　(ポインタを用いた実装を想定した例) バケットBにデータを格納する 4 7 5 6 A [0] [1] [2] [3] [4] B [0] [1] [2] [3] [4] A[0] [5] A[2] [6] A[3] バケットの先頭から順に取り出し、配列Aに戻す [7] A[4] A[1] 4 5 6 7 A’ [0] [1] [2] [3] [4] [8] [9]

問2 解答 問1：94.3%, 問2：95.8% １回目 ２回目 ３回目 K I D F A N A N Y F A N K I D B U T B U T A N Y F A N A N Y B U T K I D 問1：94.3%, 問2：95.8%

復習1 O(n2)のソート 配列の後ろから先頭に向かってスキャンし，隣り合う２つの要素の大小関係が逆であったら入れかえる 未ソート 配列の後ろから先頭に向かってスキャンし，隣り合う２つの要素の大小関係が逆であったら入れかえる 現在処理対象となっているデータを，整列済みのデータ列内の適切な位置に挿入する 整列されていない部分から最小要素を選び，先頭と入れかえる処理を繰り返す 1 3 5 9 10 7 20 17 6 3 5 8 10 11 7 ソート済 未ソート 1 3 5 9 10 7 20 17 18 入れかえ 最小値

復習2　　 A[2] A[0] A[4] A[1] A[3] 1 4 6 2 配列 A バケットB [1] [2] [3] [4] [0] [5] [6] 　 　　　　　　　　　O(n) 値kの要素を入れる箱(バケットB[k]、ただし、kは０≦k≦m-1)を準備し、各要素A[i]をB[A[i]]に入れたあと、バケットの中身を連結する 　　　　　　　　　　　O(n) 整列対象となるキーを，いくつかのサブキーに分割し，下位から上位の順に，サブキーをもとに安定な整列を行う 　　　　　　　　　　 O(n log n) ヒープを用いてデータの整列を行う B U T K I D A N Y F A N F A N B U T A N Y K I D 2 4 7 13

本日の内容 シェルソート クイックソート

シェルソート (p.109)

シェルソート（Shell sort） 1959年に D. L. Shellが発表したアルゴリズム 挿入ソートを変形 安定ではない

シェルソートの原理 55 74 3 45 13 87 46 30 離れたデータの組を挿入ソートで整列し，順次，要素間の距離を減らして整列を繰り返す 4つずつ離れたデータの組 13 74 3 30 55 87 46 45 右の例は4, 2, 1と間隔を減らしている 2つずつ離れたデータの組 …,121，40, 13, 4, 1ならばO（n1.25） 3 30 13 45 46 74 55 87 (3k−1)/2　k＝1,2,3・・・ 　(Knuthの解析実験) 1つずつ離れたデータの組 …,15, 7, 3, 1ではO（n1.5） 3 13 30 45 46 55 74 87 ２k−1　k＝1,2,3・・・ 整列終了

練習問題 以下のデータをシェルソートで昇順に整列しなさい 整列の間隔は4、2、1の順で減らすこと。 10, 5 , 4, 27, 2, 6, 3, 20, 1, 0, 8, 9, 7, 23, 13, 42

解答　　　 10 5 4 27 2 6 3 20 1 0 8 9 7 23 13 42 4ずつ離れたものをソートした結果 1 0 3 9 2 5 4 20 7 6 8 27 10 23 13 42 1 0 3 9 2 5 4 20 7 6 8 27 10 23 13 42 2ずつ離れたものをソートした結果 1 0 2　5 3 6 4 9 7 20 8 23 10 27 13 42 1ずつ離れたものをソートした結果 0 1 2　3 4 5 6 7 8 9 10 13 20 23 27 42

クイックソート　(p.96～)

(quick sort) 1962年に C. A. R. Hoareが発表したアルゴリズム 内部整列アルゴリズムの中で最速 不安定な整列アルゴリズム ただし，最悪の場合O (n2)

クイックソートの原理 ソートする範囲のデータから適当な軸要素(枢軸、pivot)νを選ぶ。 クイックソートの原理　 ソートする範囲のデータから適当な軸要素(枢軸、pivot)νを選ぶ。 要素をひとつずつ調べて、νより小さいグループと大きいグループに　　　　　する。 小グループと大グループ各々に上記１．と２．を適用する。 各々のグループが分割できなくなるまで分割を繰り返す。 大きな問題を小さな問題に分けて解決していく ⇒　分割統治（divide and conquer）

クイックソートの疑似コード void quicksort(int l, int r, int A[]) { int k; /* 枢軸より大きい部分の開始位置 */ 軸要素を決める; if (キーがすべて同じ) 終了; vより小さい部分と大きい部分に分割し， 大きい部分の先頭の位置kを返す; quicksort(l, k – 1,A); /* 小さい部分を整列 */ quicksort(k, r, A); /* 大きい部分を整列 */ }

軸要素(pivot)の選び方 方法1） データの中からランダムに一つ選ぶ。 方法2） ランダムに３要素選びその中央値をとる。 方法1）　データの中からランダムに一つ選ぶ。 方法2）　ランダムに３要素選びその中央値をとる。 方法3）　左からみて最初に得られた二つの異なる値 　　　　　　　の大きい方をとる。 ポイント： 小さい部分と大きい部分の要素数が 　　　　　　　　　　　　　　　　　　　　　　　.

partition()のループ変数 i, j がl～rの範囲を超えないことが保証される pivot　軸要素の位置を返す関数　 int pivot(int i, int j, int A[ ]) { int pv, k; k = i + 1; while(A[i] == A[k] && k <= j) k++; if (k > j) pv = -1; /* キーが全て同じ */ else if (A[i] >= A[k]) pv = i; 　　else pv = k; return(pv); } i k → j A 4 6 5 3 枢軸未満のキー 枢軸以上のキー が必ずそれぞれ1つ以上ある ↓ partition()のループ変数 i, j がl～rの範囲を超えないことが保証される

分割の手順 要素が軸要素 v より小さい限り l を右へ、 要素が v 以上である限り r を左へ動かす A l, r : カーソル 分割の手順　 要素が軸要素 v より小さい限り l を右へ、 　　要素が v 以上である限り r を左へ動かす i l r j A l, r : カーソル v : 枢軸

分割の手順(続き) l <= r なら １．に戻る A l > r なら分割終了 A i j l r i j l r キー＜ν 分割の手順(続き)　 l <= r なら　　　　　　　　　　　　　　　　　　　１．に戻る l > r なら分割終了 キー＞ν キー＜ν i j l r A i j l r A それぞれの部分に対して 再帰的に処理をくりかえす

分割手順の疑似コード int partition(int i, int j, int v, int A[]) { int l = i, r = j, k; for(;;){ while (A[l] < v) l++; while (A[r] >= v) r--; if(l <= r){ A[l]とA[r]を交換；lとrを1つ移動; } else ループから抜ける; k = l; return k;

v = 3の場合 l→ ←r 3 1 4 5 9 2 6 Start (1) 2 1 4 5 9 3 6 (2) A[0] A[1]

各々のグループをさらに分割 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 2 1 4 5 9 3 6 レベル2 v=2 1 2 v=5 4 3 9 6 5 1 2 終了 4 3 9 6 5 レベル3 v=4 3 4 v=9 5 6 9 キーが 全て同じ 3 4 終了 5 6 9 終了 レベル4 v=6 5 6 5 6 終了 レベル5 ソート終了

クイックソートの計算時間

最悪の場合 比較回数 7 6 5 4 3 2 1 → O ( n 2 )

まとめ バブルソート O(n2) 挿入ソート 選択ソート クイックソート O(n log n) ヒープソート O(n log n) 名称 計算量 内部/外部 安定/不安定 備考 バブルソート O(n2) 内部 安定 挿入ソート 選択ソート 不安定 クイックソート O(n log n)　 最悪O(n2) ヒープソート O(n log n) マージソート 外部 ビンソート O(n) データに制限有 基数ソート O(mn)

今後の予定 7/23 ヒープソートの演習(2階電算室に集合) 7/30 期末試験（掲示をよく見ること） 　　　　10：30〜12：00　場所は921

本日の問題　(問1) i=0, j=9, 軸要素v = 4の場合、関数partitionを実行すると配列の中身がどのように変化していくかを書け。また、分割終了時の l と r は各々いくつか。 1 2 3 4 5 6 7 8 9 3 1 4 5 9 2 6 Start (1) (2) (3)