| アルゴリズム１ |
|---|
|
◆ 挿入ソート ソート対象の配列を、先頭から１つずつデータを読み取り、その読み取ったデータを適切な場所に挿入していくやり方です。 文章だけでは分からないので、例で。
左からデータを比較していきます。まずは「８」。比較対象はないので、そのままソート済みデータにします。
次は「７」。「８」より小さいので「８」の前に挿入します。そしてソート済みデータにします。
少し飛ばして「２」の所まで来たとします。一番小さいので一番前に挿入します。
こんな感じで、配列のデータを１つずつ抜き取り、適切な場所にデータを挿入してソート済みデータとしてしまうやり方を挿入ソートと言います。 特徴として、ある程度ソートされたデータだとソート速度が速くなるらしく、シェルソートなどでも使われｔれいます。 ◆ ヒープソート（ヒープ木） 情報構造の箇所でも記述しましたけど、ヒープソートとはポインタ領域とか不要で配列のみでソート可能なアルゴリズムです。 「添字」とか出てましたけど、ただの配列の番号なので、あまり気にすることではないと思います。 図は太字が「添字」。いわゆる配列の順番を意味しています。 ヒープソートのアルゴリズムとは、データをヒープ構造化して、根のデータを取り出す。 そして残ったデータでまたヒープ構造化する。そして根のデータを取り出す ・・・・をデータがなくなるまで繰り返します。 と文章で書いても分からないので、下の様にデータがあったとします。
このあと、root の「２１」の要素を取り出し、整列済みの配列（新しい配列として作成します）に追加します。 そして今度は「２１」のデータの抜けた配列でヒープ木を作る事になります。
これをまたヒープ木にして、root に最大値が来るように入れ替え処理を行います。  これを繰り返して、上記の配列のデータがなくなるまで繰り返します。 出題傾向は、午後の方にアルゴリズムで問われるか、午前は意味的なものを問われる事が多いようです。 ちなみに計算量は O ( n log2 n )です。 ◆ シェルソート シェルソートとは、ある一定の間隔で離れたデータを比較して、そのデータ郡を比較しソート（入れ替え）処理を行います。 ソート処理が終わったら、一定の間隔の幅を狭めてデータを比較して、またソート処理を行います。 これを繰り返し行い、最終的に幅が１になったら挿入ソートでソート処理を行います。 以下が例です。 まずは幅を３つとしましょう。同じ色のブロックでソートして入れ替え処理をやっていると思ってください。
次に幅を２つに狭めます。
ある程度ソートされてきている事が分かります。 最後は幅が１つになってので、挿入ソートで処理します。
以上のやり方がシェルソートです。 ちなみに計算量は O ( n 0 ^ 1.25 )程度だそうです。 過去問題では、意味を問うものが多いです。 ソート処理自体とはあまり関係ないと思いますが、下の過去問題は何回か出てきています。 データ列 7, 2, 8, 3, 1, 9, 4, 5, 6 を手順 (1) 〜 (4) に従って整列する時、手順 (3) は何回繰り返して完了するか？ ［］は小数点以下を切り捨てた結果を表す。 (1) ［データ数］÷３ → Ｈ (2) データ列をお互いにＨ要素分だけ離れた要素の集まりからなる部分列として、それぞれを挿入法を用いて整列する。 (3) ［Ｈ］÷３ → Ｈ (4) Ｈが 0 であればデータ列の整列を完了し、0 でなければ (2) に戻る。 まず、順番にやりましょう。 (1) で、データ数は 9 なので、Ｈは 3 なります。 (2) でソート処理が入りますけど、問題とあまり関係ないので無視します。 (3) で 3 ÷ 3 でＨは 1 になります。◎（１回実行） (4) でＨは 1 なので (2) に戻ります。 (2) は同じように無視します。 (3) で 1 ÷ 3 でＨは 0.333・・・ になります。更に小数点以下切捨てなので Ｈは 0 。◎（２回実行） (4) でＨは 0 なので処理終了。 というわけで計２回となります。 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| TOPページに戻る |