第10回 ソート（1）：単純なソートアルゴリズム アルゴリズムと データ構造 第10回 ソート（1）：単純なソートアルゴリズム

先週の復習 再帰の基本 再帰関数呼び出し 再帰呼出しを使うことのメリット 再帰的アルゴリズムの作り方 再帰呼出しの時間計算量 再帰関数の応用例 ハノイの塔 8王妃問題

先週の演習問題

答え： 解説 recur(-1) : （何も実行されない） recur(0) : （何も実行されない） recur(1) : → 1 recur(2) : recur(0) 2 recur(1) → 2 21 1 recur(3) : recur(1) 3 recur(2) → 1321 1 3 21 recur(4) : recur(2) 4 recur(3) → 2141321 21 4 1321 recur(5) : recur(3) 5 recur(4) → 1321 132152141321 5 2141321 recur(6) : → recur(4) 6 recur(5) 2141321 21413216132152141321 6 132152141321 答え：

ソート（整列、ソーティング、sorting） 　 本日の内容 単純なソートアルゴリズム バブルソート 挿入ソート 選択ソート 比較によらないソート バケットソート 基数ソート シェルソート クイックソート マージソート

ソートの基本 レコードの集まりを，キーの値の大小関係に従って昇順（または降順）に並べかえる操作 ソートの対象は，複数の欄からなるレコード 身長をキーとして 降順にソート 氏名と身長欄から成るレコード． Cでは，構造体を用いて記述 青木 177 小田 158 金子 170 佐藤 174 渡辺 青木 177 佐藤 174 金子 170 渡辺 小田 158 同じキーをもつレコードが 複数ある時は連続して並ぶ

昇順、降順 昇順(ascending order) 降順(descending order) 数値の場合、小さいものから大きいものへ １，３，５，８，１０ 文字列の場合、辞書式順序 a, aa, abc, g, zz, zzzz 降順(descending order) 数値の場合、大きいものから小さいものへ １０，８，５，３，１ 文字列の場合、辞書式順序の逆 zzzz, zz, g, abc, aa, a

ソートアルゴリズムの要件 計算量 （時間的，空間的） 内部ソート ／ 外部ソート 安定 ／ 不安定 計算量　（時間的，空間的） 内部ソート　／　外部ソート ランダムアクセス可能なメモリの利用を前提とする方式か否か 安定　／　不安定 キーの値が同じデータを整列した場合に整列前の位置関係が維持されるか 10, 3, 5, 3, 1 ⇒　1, 3, 3, 5, 10 安定 10, 3, 5, 3, 1 ⇒　1, 3, 3, 5, 10 不安定

内部ソートと外部ソート 主記憶 (メモリ) ランダム 外部記憶 (磁気テープなど) シーケンシャル 主記憶 (メモリ) ランダム 外部記憶 整列したい データ ２ ５ １ ６ ７ 整列したい データ ２ ５ １ ６ ７ １０ ４０ ３ ４ ３５ １ ２ ５ ６ ７ ２ ５ １ ６ ７ 主記憶にコピー 入りきらない

安定なソート　　 同じキーをもつレコードが2つ以上ある場合に，整列前の位置関係が整列後も保たれているアルゴリズムを安定である(stable)という ５A　７　４　８　５B　３　２　 安定なアルゴリズムによる整列結果 不安定なアルゴリズムによる整列結果 ２　３　４　５A　５B　７　８　 ２　３　４　５B　５A　７　８　

ソート（整列）アルゴリズムの分類 バブルソート O(n2) 挿入ソート 選択ソート バケットソート O(n) 基数ソート O(mn) ソート（整列）アルゴリズムの分類　 名称 計算量 内部/外部 安定/不安定 備考 バブルソート O(n2) 内部 安定 挿入ソート 選択ソート 不安定 バケットソート O(n) データに制限有 基数ソート O(mn) シェルソート O（n1.25）～ O（n1.5） クイックソート O(n log n)　 最悪O(n2) マージソート O(n log n) 外部

O(n2)とO(n log n)の比較 n が大きいとき，O(n2)とO(n log n)の差は顕著 例） n = 32 = 25のとき n log2 n　=　32×log2 25 = 32×5 = 160 n = 1024 = 210のとき n2　=　220 =　1048576 ≒ 100万 n log2 n　=　1024×log2 210 = 1024×10 = 10240 ≒ 1万 6.4倍 100倍

バブルソート（bubble sort） 7 別名：単純交換ソート a [0] 7 別名：単純交換ソート 配列の後ろから先頭に向かってスキャンし，隣り合う２つの要素の大小関係が逆であったら入れかえる [1] 3 [2] 5 [3] 9 [4] 6 [5] 4 8 2 8 9 2 9 [n-1] 2

バブルソートのコード a i → [0] 整数を昇順に並べる場合 [1] void bubble_sort(int a[], int n) { int i, j; for (i = 0; i < n - 1; i++){ for (j = n - 1; j > i; j--){ if(a[j] < a[j-1]) a[j]とa[j-1]を交換; } [1] [2] [3] [4] [5] ｊ → [n-1]

バブルソートの実行例１ a[0] a[1] a[6] 1 6 1 6 4 1 6 4 3 4 1 3 7 7 1 3 1 7 1 9 8 9 9 8 8

バブルソートの実行例２ a[0] a[1] a[8] 整列前 ９ ３ ２ １ ４ ７ ５ ５ ８ i＝0のあと i＝1のあと 整列前　 ９　３　２　１　４　７　５　５　８ i＝0のあと i＝1のあと i＝2のあと １　２　３　９　４　５　５　７　８ i＝3のあと １　２　３ ４　９ ５　５　７　８ i＝4のあと １　２　３　４　５　９ ５　７　８ i＝5のあと １　２　３　４　５　５ ９　７　８ i＝6のあと １　２　３　４　５　５ ７　９ ８ i＝7のあと １　２　３　４　５　５　７　８ ９ 整列済　←

バブルソートの実行例２ a[0] a[1] a[8] 整列前 ９ ３ ２ １ ４ ７ ５ ５ ８ バブルソートの実行例２　 a[0] a[1] a[8] 整列前　 ９　３　２　１　４　７　５　５　８ i＝0のあと １　９　３　２　４　５　７　５　８ i＝1のあと １　２　９　３　４　５　５　７　８ i＝2のあと １　２　３　９　４　５　５　７　８ i＝3のあと １　２　３ ４　９ ５　５　７　８ i＝4のあと １　２　３　４　５　９ ５　７　８ i＝5のあと １　２　３　４　５　５ ９　７　８ i＝6のあと １　２　３　４　５　５ ７　９ ８ i＝7のあと １　２　３　４　５　５　７　８ ９ 整列済　←

バブルソートの実行例２ a[0] a[1] a[8] 整列前 ９ ３ ２ １ ４ ７ ５ ５ ８ 整列前　 ９　３　２　１　４　７　５　５　８ i＝0のあと １　９　３　２　４　５　７　５　８ i＝1のあと １　２　９　３　４　５　５　７　８ i＝2のあと １　２　３　９　４　５　５　７　８ i＝3のあと １　２　３ ４　９ ５　５　７　８ i＝4のあと １　２　３　４　５　９ ５　７　８ i＝5のあと １　２　３　４　５　５ ９　７　８ i＝6のあと １　２　３　４　５　５ ７　９ ８ i＝7のあと １　２　３　４　５　５　７　８ ９ 整列済　← 安定なソート

問題1 次のデータをバブルソートで昇順に並べ替える経過を示しなさい。 a[5] = {９,３,４,１,４};

i j a[0] a[1] a[2] a[3] a[4] 初期状態 ９ ３ ４ １ 4 3 2 1

i j a[0] a[1] a[2] a[3] a[4] 初期状態 ９ ３ ４ １ ４ 4 ４ １ ３ ９ ４ １ ３ ９ 3 ４ ３ １ ９ 2 ４ ３ ９ １ 1 ４ ３ ９ １ 4 1 ４ ３ ９ １ 3 1 ４ ９ ３ １ 2 1 ４ ９ ３ １ 4 2 ４ ９ ３ １ 3 2 ９ ４ ３ １ 4 3

バブルソートの計算量 全体 O(n2) 比較： ⇒ O(n2) i のループ n－1回 i=0 i=1 i=n-2 a [0] [1] [2] [3] j: n-1回 j: n-2回 j: 1回 全体 O(n2) [n-1] 比較： ⇒　O(n2) 交換：（a[j]<a[j-1]）の個数: 逆順の場合、比較の回数分交換も起こる　⇒ O(n2)

挿入ソート（insertion sort） ｉ番目の要素を０〜ｉの間の適切な位置に挿入する ソート済 a [0] [1] [i-1] [i] [n-1] 3 5 8 10 11 7 実行例 1 6 4 3 4 4 1 1 7 7 3 3 9 9 8 8 8

ｊ >= 1を満たさないのでwhileループを抜ける 挿入ソートのコード a[0] 3 2 void insertion_sort(int a[], int n) { int i, j; for (i = 1;i < n; i++){ j = i; while (j >= 1 && a[j] < a[j-1]){ a[j]とa[j-1]を交換; j--; } ｊ → i → [1] 3 2 [2] 1 [3] 4 [4] [n-1]

ｊ >= 1を満たさないのでwhileループを抜ける 挿入ソートのコード a[0] 1 2 2 1 3 void insertion_sort(int a[], int n) { int i, j; for (i = 1;i < n; i++){ j = i; while (j >= 1 && a[j] < a[j-1]){ a[j]とa[j-1]を交換; j--; } ｊ → [1] 2 i → [2] 3 [3] 4 [4] [n-1]

jは i ～ 1までの全てについて繰りかえし調べるのではなく，適切な挿入位置で止まる 挿入ソートのコード　 a[0] 2 3 2 1 3 1 2 3 void insertion_sort(int a[], int n) { int i, j; for (i = 1;i < n; i++){ j = i; while (j >= 1 && a[j] < a[j-1]){ a[j]とa[j-1]を交換; j--; } [1] 2 [2] 1 [3] ｊ → i → 4 [4] jは　i　～ 1までの全てについて繰りかえし調べるのではなく，適切な挿入位置で止まる [n-1]

番兵(Sentinel) 配列の範囲を超えないよう見張るために使用 決してa[j]とa[j-1]の交換が起きないような値を入れておくことで，コードを簡略化できる i ↓ a [0] [1] [i-1] [i] [n-1] [n] -∞ 3 5 8 10 1 ←　ｊ 番兵

挿入ソートのコード２ -∞ 3 2 3 2 1 4 a [0] ｊ → [1] 番兵を使う場合 void insertion_sort(int a[], int n) { int i, j; a[0] = -∞; for (i = 2;i <= n; i++){ j = i; while (a[j] < a[j-1]){ a[j]とa[j-1]を交換; j--; } ｊ → [1] 3 2 3 i → [2] 2 [3] 1 [4] 4 [5] 必ずa[1]>a[0] になり，ループを脱出 [n]

挿入ソートの実行例 整列前 ４ ５ ５ ７ ８ １ ２ ９ ３ 1回実行後 2回実行後 3回実行後 ４ ５ ５ ７ ８ １ ２ ９ ３ 挿入ソートの実行例　　　　 整列前　 ４　５　５　７　８　１　２　９　３ 1回実行後 2回実行後 3回実行後 ４　５　５　７　８　１　２　９　３ 4回実行後 ４　５　５　７　８　１　２　９　３ 5回実行後 １　４　５　５　７　８　２　９　３ 6回実行後 １　２　４　５　５　７　８　９　３ 7回実行後 １　２　４　５　５　７　８　９　３ 8回実行後 １　２　３　４　５　５　７　８　９ iの ループ 整列済　←

挿入ソートの実行例 整列前　 ４　５　５　７　８　１　２　９　３ 1回実行後 ４　５　５　７　８　１　２　９　３ 2回実行後 ４　５　５　７　８　１　２　９　３ 3回実行後 ４　５　５　７　８　１　２　９　３ 4回実行後 ４　５　５　７　８　１　２　９　３ 5回実行後 １　４　５　５　７　８　２　９　３ 6回実行後 １　２　４　５　５　７　８　９　３ 7回実行後 １　２　４　５　５　７　８　９　３ 8回実行後 １　２　３　４　５　５　７　８　９ iの ループ 整列済　← 安定なソート

問題2 次のデータを挿入ソートで昇順に並べ替える経過を示しなさい。 a[5] = {９,３,４,１,４};

i j a[0] a[1] a[2] a[3] a[4] 初期状態 ９ ３ ４ １ 1 2 3 4

i j a[0] a[1] a[2] a[3] a[4] 初期状態 ９ ３ ４ １ ４ ４ 1 １ ９ ３ ４ １ ９ ３ 2 ４ ９ １ ３ 3 ４ ９ １ ３ 2 3 ４ ９ ３ １ 1 3 ９ ４ ３ １ 4

挿入ソートの計算量 全体 O(n2) 比較： ⇒O(n2) 交換：（a[j]<a[j-1]）の個数≦ ⇒ O(n2) a [0] i のループ　n－1回 i=2 i=3 i=4 i=n a [0] [1] j [2] j のループは 適切な挿入位置で止まる [3] 内側（j）のループ回数 Min：0回 Max：i-1回 平均：約(i-1)/2回 比較：　　　　　　　　　　　 　⇒O(n2) 全体 O(n2) [n] 交換：（a[j]<a[j-1]）の個数≦ 　　　　　⇒ O(n2)

選択ソート（selection sort） 整列されていない部分から最小要素を選び，先頭と入れかえる処理を繰り返す i　(着目位置) 未ソート a [0] [1] [n-1] 1 3 5 9 10 7 20 17 18 入れかえ 整列されていない部分の最小値

選択ソート実行例 最小要素を選択し、それを先頭要素と交換 同様に次の最小要素を順次先頭側要素と交換 6 1 6 3 4 4 8 4 8 3 7 8 8 9 9 7 9 7 8

選択ソートのコード 1 2 3 9 9 7 3 a [0] void selection_sort(int a[], int n) [1] { int i, j, lowest, lowkey; for (i = 0;i < n - 1; i++){ lowest = i; lowkey = a[i]; for (j = i + 1; j < n; j++){ if (a[j] < lowkey){ lowest = j; lowkey = a[j]; } a[i]とa[lowest]を交換; [1] 2 i → [2] 3 9 9 [3] 7 [4] [5] 3 lowest→ ｊ → [n-1]

選択ソートの実行例 整列前 ９ ３ ４ ９ ７ ２ ５ ８ １ 1回実行後 2回実行後 3回実行後 １ ２ ３ ９ ７ ４ ５ ８ ９ 選択ソートの実行例　 整列前　 ９　３　４　９　７　２　５　８　１ 1回実行後　 2回実行後　 3回実行後 １　２　３　９　７　４　５　８　９ 4回実行後 １　２　３　４　７　９　５　８　９ 5回実行後 １　２　３　４　５　９　７　８　９ 6回実行後 １　２　３　４　５　７　９　８　９ 7回実行後 １　２　３　４　５　７　８　９　９ 8回実行後 １　２　３　４　５　７　８　９　９ iの ループ 整列済　←

選択ソートの実行例 整列前　 ９　３　４　９　７　２　５　８　１ 1回実行後　１　３　４　９　７　２　５　８　９ 2回実行後　１　２　４　９　７　３　５　８　９ 3回実行後 １　２　３　９　７　４　５　８　９ 4回実行後 １　２　３　４　７　９　５　８　９ 5回実行後 １　２　３　４　５　９　７　８　９ 6回実行後 １　２　３　４　５　７　９　８　９ 7回実行後 １　２　３　４　５　７　８　９　９ 8回実行後 １　２　３　４　５　７　８　９　９ iの ループ 整列済　← 不安定なソート

問題3 次のデータを選択ソートで昇順に並べ替える経過を示しなさい。 a[7] = {９,３,２,１,４,８,７};

i a[0] a[1] a[2] a[3] a[4] a[5] a[6] 初期状態 ９ ３ ２ １ ４ ８ ７ ０ 1 2 3 4 5

i a[0] a[1] a[2] a[3] a[4] a[5] a[6] 初期状態 ９ ３ ２ １ ４ ８ ７ ７ ８ ４ ９ ２ ３ １ ０ ７ ８ ４ ９ ３ ２ １ 1 ７ ８ ４ ９ ３ ２ １ 2 ７ ８ ９ ４ ３ ２ １ 3 ９ ８ ７ ４ ３ ２ １ 4 ９ ８ ７ ４ ３ ２ １ 5

交換：各iの最後に1回→全体でn-1回 ⇒O(n) 選択ソートの計算量 i のループ n－1回 i=0 i=1 i=2 i=n-2 a [0] [1] j [2] [3] j: n-1回 j: n-2回 j: 1回 [n-1] 全体 O(n2) 比較： ⇒　O(n2) 交換：各iの最後に1回→全体でn-1回　⇒O(n)

新しいデータを追加してから並べかえるときなど， まとめ　 全体の計算量 比較 交換 バブルソート O(n2) n(n-1)/2 回 （a[j]<a[j-1]）の個数回 挿入ソート 約n(n-1)/4 回 選択ソート n-1回 挿入ソートは，整列済みのデータに 新しいデータを追加してから並べかえるときなど， ほぼ整列済みのデータのソートが得意

演習問題

演習問題