arugo.html

整列と探索

◆整列方法
　　大小の順に並べ替える方法。
　　基本交換法、基本選択法、基本挿入法、シェルソート、クイックソート、ヒープソート、
　　マージソートなどがある。
　　　*昇順
　　　　小さい順に並べ換える
　　　*降順
　　　　大きい順に並べ換える

○基本交換法(バブルソート）
　　隣り合うデータの大小を比較し、順に並べる。
○基本選択法
　　データの最大値あるいは最小値を選択し、データの最初か最後に置くことを繰り返し
　　順に並べ　る
○基本挿入法
　　整列済みのデータに、新たにデータを挿入することを繰り返しデータを順に並べる。。
○シェルソート
　　データを一定の間隔ごとに挿入法で整列、最後は間隔を1にして基本挿入法でデータ
　　を順に並べ　る　
○クイックソート
　　中間となる基準値を決め、大きな値のグループ、小さな値のグループに分ける。
　　再び、それぞれのグループの基準値を決め、グループ分けを行い整列していく。
○ヒープソート(整列２分木法）
　　ヒープの根から最大値を取り出し、配列の最後に置く、さらにヒープを再構成し繰り返し
　　ながらデータを整列していく。
○マージソート　
　　データを複数のデータ群に分割、整列し、最後に整列されたデータ群を併合する　

◆探索法
　　配列やファイルから、特定の条件に合うデータを探し出す方法。
　
○線形探索
　・データ群から探索キーと同じキー値をもつデータを順に探索していく
　・データは整列しておく必要はない　
　・平均探索回数　（ｎ+1）/2
　・最大探索回数　　ｎ
　　*ｎはデータ件数

○２分割探索法
　・データ群を中央で２分割することを繰り返し、探索キーと同じキー値を持つデータを絞り
　　込み探索する　　
　・データを整列しておく
　・平均探索回数　log2n
　・最大探索回数　log2n+1

○ハッシュ表探索
　・ハッシュ関数を用いてデータの格納位置を得る
　・1回で探索できる　

★★★宿題：二種向け★（2000/5/24）

　n 個のデータをバブルソートを使って整列するとき，データの比較回数はどれ
か。

　ア　n

　イ　n log n

　ウ　n(n－1)／2

　エ　2^n

（解答例）

バブルは隣り合うデータを比較し、交換する。
このような場合は数字を入れて見るがいちばんですね。
.3.2.4.1のデータを昇順にバブルソートすると。
ここでデータ数を4個にしたのはｌｏｇを計算しやすくするため。
1回目

2	3	1	4
2	3	4	1
2	3	1	4

2回目

2	3	1	4
2	1	3	4

3回目

比較回数は6回です。

ア：データ数は4なので4回。×

イ：4ｌｏｇ4＝4lｏｇ2^2＝4×2log2＝4×2＝8　8回　×

ウ：（4×3）/2＝6　6回　○

エ：2＾4＝16　16回　×

■解答■(宿題メールより）
　　二種午前平成１２年春問１７

> バブルソート
> 隣り合うデータ同士を比較して、逆の順番であるときはそれらのデータを入れ替
> える。この操作を繰り返していくことで、データを整列させることができる。
> (第二種情報処理技術者試験直前整理特大号 P75より)
>
> 5個の下記のデータを小さい順にソートします。
> ５，３，４，２，１（５，３の比較）
> ３，５，４，２，１（５，４の比較）
> ３，４，５，２，１（５，２の比較）
> ３，４，２，５，１（５，１の比較）
>
> ３，４，２，１，５（３，４の比較）
> ３，４，２，１，５（４，２の比較）
> ３，２，４，１，５（４，１の比較）
> ３，２，１，４，５（４，５の比較）
> ３，２，１，４，５（３，２の比較）
> ２，３，１，４，５（３，１の比較）
> ２，１，３，４，５（３，４の比較）
> ２，１，３，４，５（４，５の比較）
> １，２，３，４，５（１，２の比較）
> １，２，３，４，５（２，３の比較）
> １，２，３，４，５（３，４の比較）
> １，２，３，４，５（４，５の比較）
> 16回の比較が行われます。といっても答えが無いので意味が違うようで・・・
> ちょっと分かりませんでした。

　どうもありがとうございました。比較で，８番目の（４，５の比較）等はやり
ません。整列済みの場所を記憶して，比較をしないようにします。ですから下の
ようになります。

> 5個の下記のデータを小さい順にソートします。
　比較前の並び
----------------------
> ５，３，４，２，１（５，３の比較）
> ３，５，４，２，１（５，４の比較）
> ３，４，５，２，１（５，２の比較）
> ３，４，２，５，１（５，１の比較）
>
> ３，４，２，１，５（３，４の比較）
> ３，４，２，１，５（４，２の比較）
> ３，２，４，１，５（４，１の比較）
>
> ３，２，１，４，５（３，２の比較）
> ２，３，１，４，５（３，１の比較）
>
> １，２，３，４，５（１，２の比較）

以上，５を比較するときは，4 + 3 + 2 + 1 = s で，s を求めます。

s = 4 + 3 + 2 + 1
s = 1 + 2 + 3 + 4
-------------------
2s = 5 + 5 + 5 + 5
= 5 * 4
s = (5 * 4)/2　でした。

> バブルソートのアルゴリズム
> → http://cec.te.kyusan-u.ac.jp/w3/tom/TEXT/Exercise1/8/sld001.htm
> アルゴリズムから考えると、n個のデータの比較回数は、
> (n-1)+(n-2)+・・・+1
> これは、初項1,公差1,項数n-1 の等差数列の和であるから
> (n-1)*{2*1+((n-1)-1)*1}/2 = n(n-1)/2

　どうもありがとうございました。

> http://www.soi.wide.ad.jp/class/97001/slides/04/022.html

　どうもありがとうございました。バブルソートの図は縦に描くと，いいですよ。
そうするといかにも泡（バブル）が上がっていくように見えます。

>消去法でいくとエが残るのですが、「データ個数の２乗」だと思うので
>正解はn^2ではないでしょうか？

　どうもありがとうございました。「データ個数の２乗」ではなくて，
「データ個数の２乗にだいたい比例」です。

> ア：?
> イ：クイックソートの平均比較回数
> ウ：正解
> エ：クイックソートの最高比較回数

　どうもありがとうございました。

>「嵯峨乃の情報処理用語辞典」を参照しました。２nとは、２のn乗のことです
>よね？

　どうもありがとうございました