Presentation is loading. Please wait.

Presentation is loading. Please wait.

データ構造とアルゴリズム論 第5章 整列(ソート)のアルゴリズム

Similar presentations


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

1 データ構造とアルゴリズム論 第5章 整列(ソート)のアルゴリズム
データ構造とアルゴリズム論 第5章 整列(ソート)のアルゴリズム 平成28年6月3日 森田 彦

2 今回成績が良くなかった学生へ 次回の挽回を期待しています!
応用課題提出率が6割に達していない学生は、もう少し応用課題に取り組む。→ 全41題 プリントをよく読んで内容を理解するように心がける。→リアルタイム理解チェックで理解度を常に確認する。 理解度確認テストに取り組む。→80点以上とれるように。 地道にこの点を積み重ねて行って下さい! 次回の挽回を期待しています!

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

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

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

6 <処理の流れ-4つのデータの昇順の場合> 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]の値確定。→完了!

7 アルゴリズムの整理 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.81参照。 (右端) この流れ図の理解が本日のポイント!

8 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.89参照

9 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.93の流れ図参照 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 ソート完了!

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

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

12 順序の決まり方(整理) 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]の比較(と交換)


Download ppt "データ構造とアルゴリズム論 第5章 整列(ソート)のアルゴリズム"

Similar presentations


Ads by Google