第10回 整列 ～ バブルソート，挿入ソート，選択ソート～ データ構造とアルゴリズム 第10回 整列 ～ バブルソート，挿入ソート，選択ソート～

子が2つとも親より小さいときは，小さい方の子と交換 解答(1)：半順序木（ヒープ） 子が2つとも親より小さいときは，小さい方の子と交換 2, 7, 4, 9, 7, 4, 12, 10, 13, 11 12 7 4 2 11 9 13 10 4 7 4 9 7 11 12 10 13 DeleteMinした結果

解答(2)　2分探索木 左部分木＜根＜右部分木 行きがけ順 1 3 2 3 1 2 2 1 3 通りがけ順 1 2 3 帰りがけ順 2 3 1 1 3 2 3 1 2分探索木を 通りがけ順に なぞるとデータが昇順に並ぶ 3 1 2 2

補足：ヒープとヒープメモリ 12 7 4 2 11 9 13 10 半順序木：節点ｖの優先度がｖの子の優先度より必ず小さいか等しい 補足：ヒープとヒープメモリ　　 半順序木：節点ｖの優先度がｖの子の優先度より必ず小さいか等しい heap ［英語］ つみかさねた山のようなもの，かたまり アルゴリズムの分野で 「ヒープ」という場合は，半順序木またはそれを配列で表現したものを指す 計算機の構造の話ででてくる「ヒープメモリ」or「ヒープ領域」とは意味が異なるので混同しないこと 12 7 4 2 11 9 13 10 静的メモリ領域 スタック領域 ヒープ領域

本日の内容 整列アルゴリズム 単純な整列アルゴリズム バブルソート 挿入ソート 選択ソート

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

昇順、降順 (ascending order) (descending order) 数値の場合、 ものから ものへ １，３，５，８，１０ 昇順、降順　　 　　　　(ascending 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 （　　　　　　）

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万

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

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

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

バブルソート（bubble sort） 7 3 配列の後ろから先頭に向かってスキャンし， 5 9 6 4 8 2 8 9 2 9 2 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--){ } [1] [2] [3] [4] [5] ｊ → [n-1]

バブルソートの実行例 a[0] a[1] a[8] 整列前 ９ ３ ２ １ ４ ７ ５ ５ ８ i＝0のあと i＝1のあと バブルソートの実行例　　 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] 整列前 ９ ３ ２ １ ４ ７ ５ ５ ８ バブルソートの実行例　　 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] 整列前 ９ ３ ２ １ ４ ７ ５ ５ ８ バブルソートの実行例　　 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 のループ n－1回 i=0 i=1 i=n-2 a [0] [1] [2] [3] j: n-1回 j: n-2回 j: 1回 [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を満たさないのでwhileループを抜ける 挿入ソートの疑似コード　 ｊ　>=　1を満たさないのでwhileループを抜ける a[0] 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]){ j--; } ｊ → i → [1] 3 [2] 1 [3] 4 [4] [n-1]

ｊ >= 1を満たさないのでwhileループを抜ける 挿入ソートの疑似コード　 ｊ　>=　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] 番兵を使う場合 i → [2] 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--; } 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

挿入ソートの計算量 全体 O(n2) 比較： ⇒O(n2) 交換：（a[j]<a[j-1]）の個数≒ c･n ⇒ O(n) 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]）の個数≒ c･n ⇒ O(n)

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

選択ソートの疑似コード 1 2 3 9 9 7 3 a [0] void selection_sort(int a[], int n) { 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[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) 交換：各iの最後に1回→全体でn-1回　⇒O(n)

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

次回の予定 バケットソート 基数ソート ヒープソート

本日の課題(1) 下記の疑似コードにしたがってソートする時，外側のforループの各 i での配列aの内容を記せ． 配列の要素数nは6とし，配列aの初期値は先頭から順に{ 8, 4, 3, 9, 1, 5 }であるものとする． void 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]を交換; }

付録：C言語の豆知識(1) 三項演算子“？ :” x = (a > b)？ a : b; ()内の条件が真なら：の左側 ()内の条件が偽なら：の右側 の値が返される． a=5, b=3 なら，条件が真なのでｘに5が入る． #define MAX(a, b) (a > b)? (a) : (b)