第5回配列とポインタの関係 - Yukihiro Iguchi, www

第1回 SunとUnix, 中央値
情報科学科
井口幸洋
[email protected]
2003/4/22
ソフトウェア実習I
1
本実習の目的
– 情報科学科の学生としての必須条件
• プログラミング言語の１つを確実に理解する必要あり
– 頭と体を実際に使って（実習して）習得するのが一番
– これができれば他の言語もすぐに習得可能
– 実社会では卒業生もC, C++, JAVA，Perl, Visual BASIC,
Assembly言語, etc.など様々な言語を短期間に理解し，開発
しなければならない
• データ構造とアルゴリズム
– どれを選ぶかによって数倍～数千倍の性能差が生じる
– 多くのプログラムを実際に書いて動かすのが理解の早道
2003/4/22
ソフトウェア実習I
2
目的
– しばらくぶりのプログラミングなので。。。。
簡単なものを実習してみましょう.
– クイックソートの応用
– 中央値を求めるプログラム
2003/4/22
ソフトウェア実習I
3
中央値（median)とは
• n個のデータを大小順にソート（整列）したとき，
その中央の位置にあるデータのこと
• nが奇数の時: m = (n+1)/2,
nが偶数の時: m = n/2 とすると
m番目の大きさのデータ
• 例
– 4 15 12 9 6 の中央値は？
– ソート後： 4 6 9 12 15
– 中央値は９
2003/4/22
ソフトウェア実習I
4
中央値を求める方法
• 方法１： n個のデータをソートしてからm番目
を取り出す．
• ソート法としてはクイックソートが効率が良い．
• 計算量は O(n log n).
• 中央値だけを取り出すのに全体を並べるの
は無駄！
• 方法２： O(n) で求める方法を考える．
2003/4/22
ソフトウェア実習I
5
中央値を求める手続き：sort(int *v, int left, int right)
配列v
[0] [1] [2] [3] [4] [5] [6] [7]
5 15
(1)
8 17
1
9 12
sort(v, 0, 7);
3
真ん中（3番目）を
pivot（軸）にする
(2)
(3)
17 15
last
=left
=0
5
1
i=1
17 15
2003/4/22
8
8
5
1
9 12
3
pivotを左端の値
と交換
right=7
i=1,...,7まででpivot
つまりv[left]よりも
小さいものを左に
集める．
9 12
ソフトウェア実習I
3
6
中央値を求める手続き(2)
(3)
last
=left
=0
i=1
17 15
8
5
1
9 12
swap(v, ++last, 1);
i=2
(4)
right=7
17 15
8
5
1
17 15
8
5
1
last=1;
9 12
swap(v, 2, 2);
(5)
3
i=1,...,7まででpivot
つまりv[left]よりも
小さいものを左に
集める．
3
last=2;
9 12
3
swap(v, 3, 3);
2003/4/22
ソフトウェア実習I
7
中央値を求める手続き(3)
この場合，他のすべてがpivotより小さいことに注意
途中を省略。。。。
(6)
17 15
8
5
1
9 12
3
last=7;
swap(v, 7, 7);
swap(v, left, last);
最後の値とpivotを交換
(7)
3 15
8
5
1
9 12 17
last=7;
何がわかったか？ pivotが入ったのが配列v[7].
v[0]～v[6]はこれより小さい．7>=3だから v[0]～v[6]の
どれかに中央値はあるはず!
2003/4/22
ソフトウェア実習I
8
中央値を求める手続き(4)
配列v
ここは考え
なくて良い
[0] [1] [2] [3] [4] [5] [6] [7]
(8)
3 15
8
5
1
9 12 17
sort(v, 0, 6);
真ん中（3番目）を
pivot（軸）にする
(9)
5 15
last
=left
(10) =0
3
1
i=1
5 15
2003/4/22
8
9 12 17
right=6
8
3
1
9 12 17
ソフトウェア実習I
pivotを左端の値
と交換
i=1,...,6まででpivot
つまりv[left]よりも
小さいものを左に
集める．
9
中央値を求める手続き(5)
last
=left
(10) =0
i=1
5 15
(11)
8
3
1
i=2
5 15
2003/4/22
right=6
9 12 17
right=6
8
3
1
i=1,...,6まででpivot
つまりv[left]よりも
小さいものを左に
集める．
last=0
9 12 17
ソフトウェア実習I
10
中央値を求める手続き(6)
i=3
(12)
5 15
right=6
8
3
1
i=4
(13)
5
3
9 12 17
right=6
8 15
1
last=0
last=1
9 12 17
pivotより小さいのでlast++と交換
5
2003/4/22
3
1 15
8
9 12 17
ソフトウェア実習I
11
中央値を求める手続き(7)
(14)
last=2
交換結果
5
1 15
8
i=5
(15)
5
(16)
3
3
9 12 17
right=6
1 15
8
1 15
8
last=2
9 12 17
right=6
i=6
5
2003/4/22
3
last=2
9 12 17
ソフトウェア実習I
12
中央値を求める手続き(8)
(16)
right=6
i=6
5
3
1 15
8
last=2
9 12 17
swap(v, 0, 1);
swap(v, left, last);
最後の値とpivotを交換
last=2
(16) left=0
1
2003/4/22
right=6
3
5 15
8
9 12 17
ソフトウェア実習I
何がわかったか？
last<=3以下だから
中央値はつぎは
どこの範囲ですか？
13
問題
last=2
(16) left=0
1
right=6
3
5 15
8
9 12 17
何がわかったか？
last<=3以下だから
中央値はつぎは
どこの範囲ですか？
sort(v, ？, ？);
2003/4/22
ソフトウェア実習I
14
解答
last=2
(16) left=0
1
right=6
3
5 15
8
9 12 17
sort(v, 3, 6);
sort(v,
,
2003/4/22
ソフトウェア実習I
何がわかったか？
last<=3以下だから
中央値はつぎは
どこの範囲ですか？
);
15
前回の模範解答のバグになりそうな所に
気が付きましたか？
• 中央値が入る場所:
(MAX_DATA+(MAX_DATA%2))/2-1
• MAX_DATA/2
• 配列の個数が奇数の時（例 7個）
– 中央値の入る場所＝MAX_DATA/2
• 配列の個数が偶数の時（例 8個）
– 中央値の入る場所≠MAX_DATA/2
• 関数sort内のif文の判定にMAX_DATA/2を使うの
は，上記の理由で勧められない．
2003/4/22
ソフトウェア実習I
16

Download Report