情報技術 1．基本選択法

2015/8/5
情報技術
～ソートアルゴリズム～
2015年7月9日
笠井俊信
１．基本選択法
• 基本選択法とは？
– 数列の中から最大の数値を探すことを繰り返
し，大きい数字の位置から確定していく
5 3 9 6
9 3 5 6
9 6 5 3
1
2015/8/5
ソートのステップ
6
6
7
7
7
7
2
2
2
6
6
6
5
5
5
5
5
5
3
3
3
3
4
4
1
1
1
1
1
3
7
7
6
2
2
2
4
4
4
4
3
1
6 2 5 3 1 7 4
suu [0] [1] [2] [3] [4] [5] [6]
i
j
p
0
0
1
3
4
1
7
7
7
7
0
5
5
6
6
i ・・・何番目に大きい数か
j ・・・どこまで数を調べたか
p ・・・ 1番大きい数の場所
１．基本選択法のアルゴリズム
（7個の数列のソート）
• iを0から5まで繰り返す
– 最大値の場所pにiを代入
– カウンタ２jにi+1を代入
– jをi+1から6まで繰り返す
• （条件分岐）suu[p] < suu[j]?
– Yesなら，pにjを代入
• jを1増やす
– tempにsuu[i]を，suu[i]にsuu[p]を，suu[p]にtempを代入
– iを1増やす
6 2 5 3 1 7 4
suu [0] [1] [2] [3] [4] [5] [6]
i ・・・何番目に大きい数か
j ・・・どこまで数を調べたか
p ・・・ 1番大きい数の場所
2
2015/8/5
２．基本交換法
• 基本交換法とは？
– 隣り合う2つの数を比較し，順序が間違ってい
たら入れ替えていくことで，最小値を右に送り
出していく
5 3 9 6
5 9 3 6
5 9 6 3
ソートのステップ
6
6
6
6
6
6
6
2
2
5
5
5
5
5
5
5
2
3
3
3
3
3
3
3
2
2
2
7
1
1
1
1
7
7
2
7
7
7
7
1
4
4
6 2 5 3 1 7 4
suu [0] [1] [2] [3] [4] [5] [6]
4
4
4
4
4
1
1
i
j
0
0
0
0
0
1
0
1
2
4
5
3
i ・・・何番目に小さい数か
j ・・・どこまで数を調べたか
3
2015/8/5
2．基本交換法のアルゴリズム
（7個の数列のソート）
• iを0から5まで繰り返す
– jを0から5-iまで繰り返す
• （条件分岐）suu[j] < suu[j+1]?
– tempにsuu[j]を，suu[j]にsuu[j+1]を，suu[j+1]にtempを
代入
• jを1増やす
– iを1増やす
6 2 5 3 1 7 4
suu [0] [1] [2] [3] [4] [5] [6]
i ・・・何番目に小さい数か
j ・・・どこまで数を調べたか
レポート課題
• 〆切：8月14日
• 提出方法：メール
– [email protected]
• 課題：
– 基本挿入法のアルゴリズムを調べ，
• 「ソートのステップ」を授業の形式を例に記述
– どんな変数を使い，どのように制御してソートしていくか
– 例と同様に途中まででOK
• そのアルゴリズムを授業の形式を例に記述
4

Download Report