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

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

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

2 第１回目テスト結果 講評はHP参照 平均点＝69.0 最高点＝97（１名） 最低点＝32（１名） 受験総数＝１35名 次回は挽回を！
平均点＝69.0　最高点＝97（１名）　最低点＝32（１名）　　受験総数＝１35名 次回は挽回を！ 10名います。 講評はHP参照

3 基礎課題提出状況(11/2) 平均提出数=21.7　(全課題数24) 要注意！ 約８割が21題以上を提出

4 応用課題提出状況（11/2） 平均提出課題数＝13.0 全て提出した人４名 11題以上提出は74%

5 ソートとは？ 幾つかのデータを、一定の基準（大きい順、小さい順等）に従って並べ替える操作 アルゴリズムの宝庫 アルゴリズム論学習の山場！
昇順 降順 （小さい順） （大きい順） アルゴリズムの宝庫 アルゴリズム論学習の山場！

6 本章（本日）の学習のねらい 基本的なソートアルゴリズムを学習し、その処理の流れを理解する。 → バブルソート、選択ソート、挿入ソート
基本的なソートアルゴリズムを学習し、その処理の流れを理解する。　　　　　　　　　　　　　　→　バブルソート、選択ソート、挿入ソート ３つのソートアルゴリズムの効率について考察する。 ソートアルゴリズムを実際のプログラムに応用する。

7 5-1　バブルソート 隣り合う２つのデータを比較し、「並べたい順になっていなければ入れ替える」という操作を繰り返す。　 デモプログラム

8 ＜処理の流れ－４つのデータの昇順の場合＞ A 10 9 12 2 ソート開始 10 9 12 2 A[1]＞A[2]なので交換する。 9
[3] [4] A 10 9 12 2 ソート開始 10 9 12 2 A[1]＞A[2]なので交換する。 9 10 12 2 A[2]＜A[3]なので交換しない。 9 10 12 2 A[3]＞A[4]なので交換する。 9 10 2 12 A[4]の値確定。 9 10 2 12 A[1]＜A[2]なので交換しない。 9 10 2 12 A[2]＜A[3]なので交換する。 9 2 10 12 A[3]の値確定。 9 2 10 12 A[1]＞A[2]なので交換する 2 9 10 12 A[1],A[2]の値確定。→完了！

9 アルゴリズムの特徴 A[1]～A[n]のデータをソートする場合。
データの末尾から順番に値が確定して行く。A[n]→A[n-1],･･･,A[i],・・・,A[2] A[i]の値を確定するためには、A[1]～A[i]までの比較が必要。→(i-1)回の比較 A[i] ｛i=n,n-1,・・・,2｝を確定するために 　A[j]＞A[j+1]の判定を｛j=1～i-1｝について行う。 　2重のループが必要　→ プリント p.75参照。 ※　A[0]～A[n-1]としている。

10 5-2 選択ソート ＜考え方－昇順の場合＞ 10 9 6 2 ソート開始時 10 9 6 2 最小値（の位置）を見つける 10 9 6 2
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.83参照

11 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.87の流れ図参照 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 ソート完了！

12 5-4 アルゴリズムの効率 比較回数と交換回数が少ないほど、効率は良い。 一般に・・・ 比較回数N： Nバブル=N選択≧N挿入
全てのペアについて比較 選択ソート (=ｎ-1) 整列済みデータの場合は、逆転する場合あり バブルソートが最も効率が悪い。 挿入ソートが効率が良い場合が多い。