i-1

データ構造とアルゴリズム論
第５章整列（ソート）
のアルゴリズム
平成28年6月3日
森田彦
今回成績が良くなかった学生へ
 応用課題提出率が6割に達していない学生は、
もう少し応用課題に取り組む。→ 全41題
 プリントをよく読んで内容を理解するように心が
ける。→リアルタイム理解チェックで理解度を常
に確認する。
 理解度確認テストに取り組む。→80点以上とれ
るように。
地道にこの点を積み重ねて行って下さい！
次回の挽回を期待しています！
ソートとは？
 幾つかのデータを、一定の基準（大きい順、
小さい順等）に従って並べ替える操作
昇順
（小さい順）
降順
（大きい順）
アルゴリズム
の宝庫
アルゴリズム論学習の山場！
本章（本日）の学習のねらい
① 基本的なソートアルゴリズムを学習し、その処
理の流れを理解する。
→ バブルソート、選択ソート、挿入ソート
② ３つのソートアルゴリズムの効率について考
察する。
③ ソートアルゴリズムを実際のプログラムに応用
する。
5-1 バブルソート
 隣り合う２つのデータを比較し、「並べたい
順になっていなければ入れ替える」という
操作を繰り返す。
デモプログラム
＜処理の流れ－４つのデータの昇順の場合＞
A
[0]
[1] [2]
[3]
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]の値確定。→完了！
アルゴリズムの整理
 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参照。
この流れ図の理解が本日のポイント！
5-2 選択ソート
 ＜考え方－昇順の場合＞
選択ソート
10
9
6
2
ソート開始時
10
9
6
2
最小値（の位置）を見つける
10
9
6
2
2
9
6 10
1番目のデータと交換する
1番目データの値確定
2
9
6 10
最小値（の位置）を見つける
2
9
6 10
2番目のデータと交換する
2
6
9 10
2番目データの値確定
という操作を繰り返す。
流れ図→p.89参照
5-3 挿入ソート
 部分的に整列されている場合に効果的
例：A[1]～A[3]が整列済み（昇順）
[1] [2]
[3] [4] [5]
正しい位置に
余分な比較をし
なくて良い。
A 1
2
3
9
5
A[4]を挿入 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
ソート完了！
5-4 アルゴリズムの効率
 比較回数と交換回数が少ないほど、効率
n：データ個数
は良い。
全てのペアについて比較 =n(n-1)/2
 一般に・・・
比較回数N： Nバブル=N選択≧N挿入
交換回数N： Nバブル=N挿入、 N選択 =ｎ-1
バブルソートが最も効率が悪い。
プリント5-4
節参照！
一般には、挿入ソートが効率が良い場合が多い。
学習に当たって
 ソート（処理）はアルゴリズム論の山場となる重
要なところです。
 各ソートの処理の流れを、シミュレーションプロ
グラムを利用してよく理解して下さい。
 本日の学習のポイントは、各ソートの流れ図を
理解できるかどうかです。→トレースして流れを
確認できればOK
 理解できない場合は「どの部分が理解できない
のか？」を自分なりにしぼって森田に尋ねて下
さい。
 また友人同士で教え合うことを奨励します。
 【応用課題5-A】まで終えた学生は、演習を終え
て結構です。
位置が
決定す
る要素
順序の決まり方（整理）
A[0] A[1] ・・・ A[i]
・・・ A[n-2] A[n-1]
i
n-1
A[j]とA[j+1]の比較（と交換）
j=0～n-2
n-2
A[j]とA[j+1]の比較（と交換）
j=0～n-3
・・・
i
A[j]とA[j+1]の比較（と交換）
j=0～ ?i-1
・・・
2
A[j]とA[j+1]の比較（と交換）
j=0～1
1
A[j]とA[j+1]の比較（と交換）
j=0

Download Report