プログラミング 4 整列アルゴリズム.

Presentation on theme: "プログラミング 4 整列アルゴリズム."— Presentation transcript:

1 プログラミング 4 整列アルゴリズム

2 整列処理 決められた順序に従ってデータを並べ替える 並び変えの順序 どこがポイントか 計算機にとって重要な処理
整列されたデータが前提の処理もある（例：二分探索） 何種類も手順（アルゴリズム）が知られている 数値でない場合もある（文字列など） 並び変えの順序 昇順：小→大，小さい順，数上がり 降順：大→小，大きい順，数下がり どこがポイントか 各アルゴリズムの基本戦略，特徴 計算量（平均の場合と最悪の場合）

3 扱うアルゴリズム コードまで書ける必要がある（簡単で，計算量が大き い）
バブルソート 単純選択ソート 単純挿入ソート アルゴリズムを理解し，ヒントがあればコードが書け る（難しく，計算量が小さい） マージソート クイックソート 以降の例では数値を昇順に整列させる

4 バブルソート(1) 基本戦略 隣どうしで並べたい順序と違っていたら入れ替える （これを繰り返せばそのうち完了する）
基本戦略 隣どうしで並べたい順序と違っていたら入れ替える （これを繰り返せばそのうち完了する） 特徴 コードが短くて簡単 ひたすら交換 単純交換ソートともいう

5 31 41 59 26 53 58 97 93 入れ替えない 31 41 59 26 53 58 97 93 入れ替えない 31 41 59 26 53 58 97 93 入れ替える 31 41 26 59 53 58 97 93 入れ替える 31 41 26 53 59 58 97 93 入れ替える 31 41 26 53 58 59 97 93 入れ替えない 31 41 26 53 58 59 97 93 入れ替える 31 41 26 53 58 59 93 97 これで 1 セット この時点で最大値の位置が確定

6 31 41 59 26 53 58 97 93 31 41 26 53 58 59 93 97 31 26 41 53 58 59 93 97 26 31 41 53 58 59 93 97 26 31 41 53 58 59 93 97 26 31 41 53 58 59 93 97 26 31 41 53 58 59 93 97 26 31 41 53 58 59 93 97 26 31 41 53 58 59 93 97

7 バブルソート(4) void bubsort(int a[], int n) { int i, j, t; for (i = n - 1; i > 0; i--) { for (j = 0; j < i; j++) { if (a[j] > a[j + 1]) { t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; } } } return; } 繰り返しの範囲に注意

8 バブルソート(5) 2 重の繰り返しで書かれる バブルソートの計算量は O(n2) 外側の繰り返しは n - 1 回（O(n)）

9 単純選択ソート(1) 基本戦略 未整列部分の最小値を，未整列部分の先頭と入れ替え る 特徴 コードが簡単 最小値問題＋交換
基本戦略 未整列部分の最小値を，未整列部分の先頭と入れ替え る 特徴 コードが簡単 最小値問題＋交換 セレクションソートともいう

10 31 41 59 26 53 58 97 93 最小値は 26 26 41 59 31 53 58 97 93 最小値は 31 26 31 59 41 53 58 97 93 最小値は 41 26 31 41 59 53 58 97 93 最小値は 53 26 31 41 53 59 58 97 93 最小値は 58 26 31 41 53 58 59 97 93 最小値は 59 26 31 41 53 58 59 97 93 最小値は 93 26 31 41 53 58 59 93 97

11 単純選択ソート(3) void selsort(int a[], int n) { int i, j, k, t; for (i = 0; i < n - 1; i++) { k = i; /* 仮の最小は a[i] にあるとする */ for (j = i + 1; j < n; j++) { if (a[k] < a[j]) k = j; /* 仮の最小を更新 */ } t = a[k]; a[k] = a[i]; a[i] = t; } return; } 外側の繰り返しの中身が a[i]～a[n - 1] の「最小値探し」に なっている

12 単純選択ソート(4) 2 重の繰り返しで書かれる 単純選択ソートの計算量は O(n2) 外側の繰り返しは n - 1 回（O(n)）

13 単純挿入ソート(1) 基本戦略 整列済み部分の適切な箇所に，未整列部分の先頭を差 し込む
基本戦略 整列済み部分の適切な箇所に，未整列部分の先頭を差 し込む 特徴 ほぼ整列済みのデータに対してちょっとだけ速い 挿入箇所を決めるコードが混乱しやすい インサーションソートともいう

14 31 41 59 26 53 58 97 93 41 を挿入 31 41 59 26 53 58 97 93 59 を挿入 31 41 59 26 53 58 97 93 26 を挿入 26 31 41 59 53 58 97 93 53 を挿入 26 31 41 53 59 58 97 93 58 を挿入 26 31 41 53 58 59 97 93 97 を挿入 26 31 41 53 58 59 97 93 93 を挿入 26 31 41 53 58 59 93 97

15 単純挿入ソート(3) void inssort(int a[], int n) { int i, j, t; for (i = 1; i < n; i++) { t = a[i]; for (j = i - 1; j >= 0; j--) { if (a[j] < t) break; a[j + 1] = a[j]; } a[j + 1] = t; } return; } 内側の繰り返しで挿入箇所を探しながら要素を 1 つずつ後ろに ずらしている

16 単純挿入ソート(4) 2 重の繰り返しで書かれる 単純挿入ソートの計算量は O(n2) 外側の繰り返しは n - 1 回（O(n)）

17 マージソート(1) 基本戦略 「2 つの整列済み部分を併合してより大きな整列済み 部分を作る」を繰り返し，全体を整列させる
基本戦略 「2 つの整列済み部分を併合してより大きな整列済み 部分を作る」を繰り返し，全体を整列させる 特徴 安定して速い 再帰呼び出しを使う

18 マージソート(2) 31 41 59 26 53 58 97 93 31 41 26 59 53 58 93 97 26 31 41 59 53 58 93 97 26 31 41 53 58 59 93 97

19 マージソート(3) マージソートの実装では一般に再帰を使う 最初に 1 個になるまで半分ずつ，半分ずつ，……，の分割を 再帰で行う
再帰から戻るときに分割された部分を統合する

20 マージソート(4) void mergesort(int a[], int w[], int l, int r) { int i, j, k, m; if (l >= r) return; /* 再帰を止める */ m = (l + r) / 2; mergesort(a, w, l, m); /* 分割：前半 */ mergesort(a, w, m + 1, r); /* 分割：後半 */ /* 併合 */ i = l; j = l; k = m + 1; while (j <= m && k <= r) { if (a[j] < a[k]) { w[i] = a[j]; i++; j++; } else { w[i] = a[k]; i++; k++; } } while (j <= m) { w[i] = a[j]; i++; j++; } while (k <= r) { w[i] = a[k]; i++; k++; } /* 作業用配列からもとの配列に書き戻し */ for (i = l; i <= r; i++) { a[i] = w[i]; } return; }

21 マージソート(5) 再帰と繰り返しで書かれる マージソートの計算量は O(log n) × O(n) → O(n log n)
再帰呼び出しの深さは n に対して O(log n) 回 データ数が倍になると分割回数が 1 回増える 併合の処理は，毎回すべての要素に対して行われる：O(n) 回 マージソートの計算量は O(log n) × O(n) → O(n log n) 一方で作業用配列が必要になる（空間計算量 O(n)）

22 クイックソート(1) 基本戦略 「数が小さい山」と「数が大きい山」に大雑把に分け ることを再帰的に繰り返す
基本戦略 「数が小さい山」と「数が大きい山」に大雑把に分け ることを再帰的に繰り返す 特徴 実用上最速 再帰呼び出しを使う 「大雑把に分ける」のがうまくいかないと遅くなって しまう

23 クイックソート(2) クイックソートの実装には一般に再帰を使う
「小さい山」「大きい山」それぞれについて同じことを実行 し，要素が 1 個になるまで再帰 分類が終わったら再帰

24 クイックソート(3) void quicksort(int a[], int l, int r) { int ll, rr, piv, t; if (l >= r) return; piv = a[(l + r) / 2]; ll = l; rr = r; while (ll <= rr) { while (a[ll] < piv) ll++; while (a[rr] > piv) rr++; t = a[ll]; a[ll] = a[rr]; a[rr] = t; ll++; rr--; } quicksort(a, l, rr); /* 「小さい山」も同様に */ quicksort(a, ll, r); /* 「大きい山」も同様に */ return; }

25 クイックソート(4) 再帰と繰り返しで書かれる クイックソートの計算量は O(log n) × O(n) → O(n log n)
再帰呼び出しの深さは n に対して O(log n) 回 データ数が倍になると分割回数が 1 回増える 振り分けの処理は，毎回すべての要素に対して行われる： O(n) 回 クイックソートの計算量は O(log n) × O(n) → O(n log n) 分割が偏る（1 個と残り全部）になると再帰の深さが O(n) になり，計算量が O(n2) になる（最悪計算量）