第12回 ソート（3）: シェルソート、クイックソート

Presentation on theme: "第12回 ソート（3）: シェルソート、クイックソート"— Presentation transcript:

1 第12回 ソート（3）: シェルソート、クイックソート
アルゴリズムと データ構造 第12回 ソート（3）: シェルソート、クイックソート

2 先々週の復習 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 入れかえ 最小値

3 先週の復習 バケットソート O(n) 基数ソート O(n)
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) 整列対象となるキーを，いくつかのサブキーに分割し，下位から上位の順に，サブキーをもとに安定な整列を行う B U T K I D A N Y F A N F A N B U T A N Y K I D

4 先週の演習問題 (問1)次の5個の整数　{4, 7, 5, 6, 7}をバケットソートでバケットB[i]( 0 ≦ i < 10) を用いて整列する手順を図を用いて説明せよ。

5 4 7 5 6 B [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 4 5 6 7
問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]

6 問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]

7 (B U T ), ( F A N ), ( A N Y ), ( K I D )
(問2)次の３文字の系列を基数ソートで辞書式順序に並べていく過程を示せ。 (B U T ), ( F A N ), ( A N Y ), ( K I D ) １回目 ２回目 ３回目

8 問2 解答 １回目 ２回目 ３回目 K I D F A N A N Y F A N K I D B U T B U T A N Y

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

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

11 シェルソート 単純挿入ソートの特徴 シェルソートの考え方 ソート済みに近い場合は高速 挿入先が遠く離れていると移動回数が増大
1 1 1 2 2 2 3 3 4 3 4 4 5 5 5 6 シェルソートの考え方 単純挿入ソートの長所を生かしつつ、回数の多い移動を避ける 最初にまずグループ化を行い、グループ内で大まかにソート（地ならし） グループを次第に小さくしていき、最終的に単純挿入ソートを行ってソート完了 前処理を含めても、移動回数が少なくてすみ、全体として高速化

12 シェルソートの実例 4-ソート ２-ソート １-ソート 8 8 7 1 1 3 4 4 2 2 7 7 8 6 6 3 4 3 5 5 3

13 シェルソート シェルソートのプログラム for (h = n / 2; h > 0; h / 2)
for (i = h; i < n; i++) { int tmp = a[i]; for (j = i - h; j >= 0 && a[j] > tmp; j -= h) a[j + h] = a[j]; a[j + h] = tmp; }

14 シェルソート 増分の選択 ある値から減少して1になればよい
増分のとり方によっては、同じグループ内でのみソートして、グループ分けが十分に機能しなくなる 増分が互いに倍数にならないようにする h = ・・・、121、40、13、4、1 1から始め、3倍して1を足していく 最初が大きすぎても効果なし：n / 9を超えない値

15 シェルソート 適切増分シェルソートのプログラム for (h = 1; h < n / 9; h = h * 3 + 1) ;
for (i = h; i < n; i++) { int tmp = a[i]; for (j = i - h; j >= 0 && a[j] > tmp; j -= h) a[j + h] = a[j]; a[j + h] = tmp; }

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

17 解答 4ずつ離れたものをソートした結果 2ずつ離れたものをソートした結果 　 1ずつ離れたものをソートした結果 　

18 シェルソート（Shell sort）のまとめ
挿入ソートを変形 計算量O（n1.25）～O（n1.5） 安定ではない

19 クイックソート クイックソートとは ただし，最悪の場合O (n2) 1962年に C. A. R. Hoareが発表したアルゴリズム
内部整列アルゴリズムの中で最速 不安定な整列アルゴリズム ある要素を決め、その要素より大きいグループと小さいグループに分類 ある要素：枢軸 各グループで枢軸を決め直して同じように分割 計算量O（n log n） ただし，最悪の場合O (n2)

20 クイックソートの原理 ソートする範囲のデータから適当な軸要素(枢軸、pivot) Xを選ぶ。
小グループと大グループ各々に上記１．と２．を適用する。 各々のグループが分割できなくなるまで分割を繰り返す。 実行例１ 8 3 6 5 5 4 7 2 1 4 2 2 3 1 5 6 6 8 7 1 2 2 4 4 3 5 5 6 8 8 7 1 2 3 4 5 6 7 8

21 分割の手順 枢軸をx、配列左端をpl、配列右端をprとし pl位置の要素がxより大きくなるまでplを右に移動
pr位置の要素がxより小さくなるまでprを左に移動 pl、pr両位置の要素を交換 操作を続け、plとprの位置が交差した時点で終了 配列左端からpl位置の1つ前まで：枢軸より小さい集合 pr位置の1つ後から配列右端まで：枢軸より大きい集合 実行例２ 5 5 3 7 7 1 1 4 4 2 6 6 6 2 2 6 3 7 3 9 9 8 8 pl pr 枢軸以下 枢軸以上

22 クイックソート ソートの手順 分割されたグループそれぞれに、同じ処理を再度適用して再分割
分割されたグループの要素数が1になった時点で分割終了 一種の分割統治法：再帰で簡単に実現

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

24 枢軸の選択 枢軸の選び方がクイックソートの効率に影響 できるだけ配列の値の中央値が望ましい
配列の値の最小値または最大値を選ぶと最悪 できるだけ配列の値の中央値が望ましい ただし厳密に求める処理に時間がかかると本末転倒 方針1：先頭要素、中央要素、最後尾要素の3値の中間値を使う 方針2：方針1に加え、3値をソートして、中央要素と最後尾1つ前の値を入れ替え、ソート範囲を3要素分絞る 先頭は必ず枢軸以下、最後尾とその手前は必ず枢軸以上の値になっているので、それぞれの内側をソート範囲とすればよくなる

25 実行例３ Ｘ= 3の場合 pl→ ←pr 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 分割終了 pr = 2 pl = 3 pl, pr : カーソル v : 枢軸

26 実行例３：各々のグループをさらに分割 2 1 4 5 9 3 6 レベル2 1 2 4 3 9 6 5 1 2 4 3 9 6 5 レベル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 Ｘ=2 1 2 Ｘ=5 4 3 9 6 5 1 2 終了 4 3 9 6 5 レベル3 Ｘ=4 3 4 Ｘ=9 5 6 9 キーが 全て同じ 3 4 終了 5 6 9 終了 レベル4 Ｘ=6 5 6 5 6 終了 レベル5 ソート終了

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

28 最悪の場合 = { n ( n - 1) } / 2 比較回数 7 6 5 4 3 2 1 Σｉ → O ( n 2 ) ｎ＝ 8
ｎ＝　8 比較回数 7 ：　即ち　n-1 6 5 4 3 2 1 選択ソートの実行と同じようになり Σｉ i=1 n-1 = { n ( n - 1) } / 2 → O ( n 2 )

29 クイックソートのまとめ ただし，最悪の場合O (n2) 1962年に C. A. R. Hoareが発表したアルゴリズム
内部整列アルゴリズムの中で最速 不安定な整列アルゴリズム ある要素を決め、その要素より大きいグループと小さいグループに分類 ある要素：枢軸 各グループで枢軸を決め直して同じように分割 計算量O（n log n） ただし，最悪の場合O (n2)

30 ソート全体のまとめ バブルソート O(n2) 挿入ソート 選択ソート バケットソート O(n) 基数ソート シェルソート クイックソート
名称 計算量 内部/外部 安定/不安定 備考 バブルソート O(n2) 内部 安定 挿入ソート 選択ソート 不安定 バケットソート O(n) データに制限有 基数ソート シェルソート O（n1.25）～ O（n1.5） クイックソート O(n log n)　 最悪O(n2)

31 演習問題 次の配列を、クイックソートにより並べ替える。
並べ替え領域の左端の添え字を pl、右端の添え字を pr と設定したとき、枢軸は (pl+pr)/2（小数点以下切り捨て）で示される添え字の位置とする（この配列では添え字 5 の 59）。ここで 1. pl 位置の値が枢軸の値以上になるまで pl を右へずらす。 2. pr 位置の値が枢軸の値以下になるまで pr を左へずらす。 3. pl 位置の値と pr 位置の値を入れ替える。 4. pl と pr が交差して入れ替わるまで、1. から 3. までを繰り返す。 という操作を行うと、配列は となり、添え字 0 から 5 までの集合と 6 から 11 までの集合に分割される。このとき、以下の問いに答えよ。 (1) 添え字 0 から 5 までの集合において、pl、pr および枢軸の位置を再設定し、同様に分割したとき、分割後の配列の並びと pl、pr の添え字位置を示せ。 (2) 添え字 6 から 11 までの集合において、pl、pr および枢軸の位置を再設定し、同様に分割したとき、分割後の配列の並びと pl、pr の添え字位置を示せ。