ext-web.edu.sgu.ac.jp

データ構造とアルゴリズム論
第５章整列（ソート）
のアルゴリズム
平成17年11月22日
森田彦
第１回目テスト結果
平均点＝62.8 最高点＝96 最低点＝27 受験者＝137名
第1回目テスト（11/15実施）　受験者総数＝137名
最高点=96　最低点=27　平均点=62.8
50
45
40
度数（人数）
35
30 次回は挽回を！
25
20
14名います。
15
10
5
0
20～39
40～49
50～59
講評はHP参照
60～69
70～79
80～89
90～100
成績と（プリントの）読み方の相関
成績と（プリントの）読み方の相関
67
66
テスト平均点
65
64
63
62
61
60
59
58
57
良く読む
課題部分のみ読む
「プリントを良く読む」グループの方が成績が良い！
プリントを良く読んで理解する習慣を身につ
けて下さい。
成績と学習スタイルの相関
成績と学習スタイルの相関
66
テスト平均点
64
62
60
58
56
54
52
50
内容把握優先課題作成優先
まず人に聞く
「学習内容を把握してから課題作成」グループが最も
成績がよい。
学習内容の理解に重点を！
アンケート自由記述から
 今後内容について行けるか不安に思っていま
す。
 テスト勉強をしていて、プリントをよく読めば理解
できることに気付きました。
 前期と比べて授業内容が格段にレベルアップし
ているような気がした。もっと気合いを入れて取
り組まなければならないと思った。
 参考書でお薦めのものがあれば、授業中にスク
リーンに表示したらどうでしょうか？
「やさしいJava活用編」高橋麻奈ソフトバンク社 \2,600
基礎課題提出状況(11/15)
基礎課題提出状況（11/15）　平均=21.9（昨年21.7）　［全課題24題］
90
80
70
度数（人数）
60
50
'04年度
'05年度
要注意！
40
30
20
10
0
1～10
11～15
16～20
提出数
昨年より若干速いペース
21～22
23～24
62%が23題以上を提出
応用課題提出状況（11/15）
応用課題提出状況（11/15）　平均12.92（昨年13.01）
全課題22題
60
度数（人数）
50
40
30
20
10
0
0
1～5
6～10 11～15 16～19 20～22
提出数
昨年とほぼ同じペース
全
て
提
'04年度出
'05年度
し
た
人
7
名
11題以上提出は69%
ソートとは？
 幾つかのデータを、一定の基準（大きい順、
小さい順等）に従って並べ替える操作
昇順
（小さい順）
降順
（大きい順）
アルゴリズム
の宝庫
アルゴリズム論学習の山場！
本章（本日）の学習のねらい
① 基本的なソートアルゴリズムを学習し、その処
理の流れを理解する。
→ バブルソート、選択ソート、挿入ソート
② ３つのソートアルゴリズムの効率について考
察する。
③ ソートアルゴリズムを実際のプログラムに応用
する。
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.75参照。
この流れ図の理解が本日のポイント！
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.83参照
5-3 挿入ソート
 部分的に整列されている場合に効果的
例：A[1]～A[3]が整列済み（昇順）
[1] [2]
[3] [4] [5]
正しい位置に
余分な比較をし
なくて良い。
A 1
2
3
9
5
A[4]を挿入 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
ソート完了！
5-4 アルゴリズムの効率
 比較回数と交換回数が少ないほど、効率
は良い。
全てのペアについて比較
 一般に・・・
比較回数N： Nバブル=N選択≧N挿入
交換回数N： Nバブル=N挿入≧N選択 (=ｎ-1)
整列済みデータの場合は、逆転する場合あり
バブルソートが最も効率が悪い。
挿入ソートが効率が良い場合が多い。
プリント参
照！
学習に当たって
 ソート（処理）はアルゴリズム論の山場となる重
要なところです。
 各ソートの処理の流れを、シミュレーションプロ
グラムを利用してよく理解して下さい。
 本日の学習のポイントは、各ソートの流れ図を
理解できるかどうかです。
 理解できない場合は「どの部分が理解できない
のか？」を自分なりに絞って補助員や指導員に
尋ねて下さい。
 また友人同士で教え合うことを奨励します。
位置が
決定す
る要素
順序の決まり方（整理）
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