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

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

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

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

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

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

5 ＜処理の流れ－４つのデータの昇順の場合＞ A 10 9 12 2 ソート開始 10 9 12 2 A[0]＞A[1]なので交換する。 9
[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]の値確定。→完了！

6 アルゴリズムの整理 A[0]～A[n-1]のデータをソートする場合。 データの末尾から順番に値が確定して行く。
A[0],A[1],・・・,A[i],・・・,A[n-2],A[n-1] A[i]の値を確定するためには、A[0]～A[i]までの比較が必要。→i回の比較 A[i] ｛i=n-1,n-2,・・・,1｝を確定するために 　A[j]＞A[j+1]の判定を｛j=0～i-1｝について行う。 　2重のループが必要　→ プリント p.71参照。 （右端） この流れ図の理解が本日のポイント！

7 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.79参照

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

9 順序の決まり方（整理） i n-1 j=0～n-2 n-2 j=0～n-3 i j=0～ ? i-1 j=0～1 2 j=0 1 ・・・
位置が決定する要素 順序の決まり方（整理） A[0] A[1] ・・・ A[i] A[n-1] A[n-2] i n-1 j=0～n-2 A[j]とA[j+1]の比較（と交換） n-2 j=0～n-3 A[j]とA[j+1]の比較（と交換） ・・・ i A[j]とA[j+1]の比較（と交換） j=0～ ? i-1 ・・・ j=0～1 2 A[j]とA[j+1]の比較（と交換） j=0 1 A[j]とA[j+1]の比較（と交換）