データ構造とアルゴリズム論 第５章 整列（ソート）のアルゴリズム

Presentation on theme: "データ構造とアルゴリズム論 第５章 整列（ソート）のアルゴリズム"— Presentation transcript:

1 データ構造とアルゴリズム論 第５章 整列（ソート）のアルゴリズム
データ構造とアルゴリズム論 第５章　整列（ソート）のアルゴリズム 平成29年11月22日 森田　彦

2 バブルソート A 10 9 12 2 ソート開始 10 9 12 2 A[0]＞A[1]なので交換する。 9 10 12 2
[2] [3] A 10 9 12 2 ソート開始 10 9 12 2 A[0]＞A[1]なので交換する。 9 10 12 2 A[1]＜A[2]なので交換しない。 9 10 12 2 A[2]＞A[3]なので交換する。 9 10 2 12 A[3]の値確定。 9 10 2 12 A[0]＜A[1]なので交換しない。 9 10 2 12 A[1]＜A[2]なので交換する。 9 2 10 12 A[2]の値確定。 9 2 10 12 A[0]＞A[1]なので交換する 2 9 10 12 A[0],A[1]の値確定。→完了！

3 5-2 選択ソート ＜考え方－昇順の場合＞ 選択ソート 10 9 6 2 ソート開始時 10 9 6 2 最小値（の位置）を見つける 10
5-2　選択ソート ＜考え方－昇順の場合＞ 選択ソート 10 9 6 2 ソート開始時 10 9 6 2 最小値（の位置）を見つける 10 9 6 2 1番目のデータと交換する 2 9 6 10 1番目データの値確定 2 9 6 10 最小値（の位置）を見つける 2 9 6 10 2番目のデータと交換する 2 6 9 10 2番目データの値確定 という操作を繰り返す。 流れ図→p.78参照

4 5-3 挿入ソート 部分的に整列されている場合に効果的 例：A[1]～A[3]が整列済み（昇順） 余分な比較をしなくて良い。 A[4]を挿入
5-3　挿入ソート 部分的に整列されている場合に効果的 例：A[1]～A[3]が整列済み（昇順） 余分な比較をしなくて良い。 正しい位置に [1] [2] [3] [4] [5] A[4]を挿入 A 1 2 3 9 5 p.83の流れ図参照 1 2 3 9 5 A(3)＜A(4)なので交換しない 1 2 3 9 5 A(1)～A(4)まで整列済み 1 2 3 9 5 A(5)を挿入 1 2 3 9 5 A(4)＞A(5)なので交換する 1 2 3 5 9 A(3)＜A(4)なので交換しない 1 2 3 5 9 ソート完了！

5 5-4 アルゴリズムの効率 比較回数と交換回数が少ないほど、効率は良い。 一般に・・・ 比較回数N： Nバブル=N選択≧N挿入
全てのペアについて比較 =n(n-1)/2 =ｎ-1 バブルソートが最も効率が悪い。 プリント5-4節参照！ 一般には、挿入ソートが効率が良い場合が多い。

6 学習に当たって ソート（処理）はアルゴリズム論の山場となる重要なところです。
挿入ソートの処理の流れを、シミュレーションプログラムを利用してよく理解して下さい。 本日の学習のポイントは、挿入ソートの流れ図を理解できるかどうかです。→トレースして流れを確認できればOK 理解できない場合は「どの部分が理解できないのか？」を自分なりにしぼって森田に尋ねて下さい。 【応用課題5-A】まで終えた学生は、演習を終えて結構です。