第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 バケットソート O(n) 基数ソート O(n) ヒープソート O(n log n) 2 4 7 13 復習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が発表したアルゴリズム 挿入ソートを変形 計算量O（n1.25）～O（n1.5） 安定ではない

シェルソートの原理 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（n log n） ただし，最悪の場合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 を左へ動かす キー＜v キー ≧ v A 分割の手順　 要素が軸要素 v より小さい限り l を右へ、 要素が v 以上である限り r を左へ動かす l キー＜v i r キー ≧ v j A l, r : カーソル v : 枢軸

分割の手順(続き) l <= r なら A[l] とA[r] を入れかえて １．に戻る A l > r なら分割終了 A i j 分割の手順(続き)　 l <= r なら A[l] とA[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 A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] 3 1 4 5 9 2 6 Start (1) 2 1 4 5 9 3 6 (2) 2 1 4 5 9 3 6 分割終了 r = 2 l = 3

各々のグループをさらに分割 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 ソート終了

クイックソートの計算時間 分割の段数≒log2 n 各段での時間 O ( n ) 平均時間 → O ( n log n )

最悪の場合 比較回数 7 6 5 4 3 2 1 Σｉ i=1 n-1 = { n ( n - 1) } / 2 → 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 期末試験（掲示をよく見ること）

本日の問題　(問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)