データの整列方法

データ整列方法は「整列と探索」のページを参考にしてください。

★★★宿題：二種向け★（2000/3/14）

　データの整列方法に関する記述のうち，正しいものはどれか。

　ア　クイックソートは，ある間隔で要素を取り出した部分列を整列し，更に間
　　隔をつめた部分列を取り出して整列する方法である。

　イ　シェルソートは，隣り合う要素を比較して，大小の順が逆であれば，それ
　　らの要素を入れ替えるという操作を繰り返して行う方法である。

　ウ　バブルソートは，中間的な基準値を決めて，それより大きな値の要素を集
　　めた区分と小さな値の要素を集めた区分とに振り分ける。次にそれぞれの区
　　分の中で同様な処理を繰り返す方法である。

　エ　ヒープソートは，未整列の部分を部分木で表し，そこから最大値又は最小
　　値を取り出して既整列の部分に移す。この操作を繰り返して，未整列部分を
　　縮めてゆく方法である。

（解答）

ア：シェルソートの説明
イ：バブルソートの説明
ウ：クイックソートの説明
エ：正解

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

>ア：シェルソートの説明
>イ：バブルソートの説明
>ウ：クイックソートの説明
>エ：正解

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

>ア クイックソート
> 配列中から１件のデータを選び、これより大きなデータを上位に、小さな
> データを下位に移動する。
> 大きいデータ群と小さいデータ群に対して別々に同様の操作を行う。
> これをさらに細かく繰り返すとソートが完了する。
>イ シェルソート
> 配列中のデータから、まず一定間隔（例えばｍ）ごとにデータをとって
> 整列する。
> これをずらしながらｍ回繰り返せば、全データをｍグループに分けて整列
> したことになり、大まかには整列される。
> 間隔幅を変えて大まかな整列を繰り返せば、整列の状態に近づく。
> そこで挿入ソートを行えば、効率よくソートが完了する。
>ウ バブルソート
> 配列中のデータの隣り合った二つを比較し、逆順であれば入れ替える。
> これを何回も繰り返し、ソートを完了する。
>エ 正解
>
>参考：「合格情報処理２月号付録 情報システム辞典」

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

>クイックソート[quick sort]
>基準となる値（軸）を決め、軸よりも小さければ軸の左へ、
>大きければ軸の右側に集めて軸で２当分し、分割された
データ列に対しても、おなじような分割をくりかえす。
>「情報処理用語辞典」p.126　新星出版社
>
>シェルソート[shell sort]
>データを飛び（ギャップという）のあるいくつかの部分に
分けておおざっぱに整列してから基本挿入法をを適用する
>整理法。
>「情報処理用語辞典」p.166　新星出版社
>
>バブルソート[bubble sort]
>隣同士のデータを順に比較して、大小関係が逆ならば
>交換を行う整列法。
>「情報処理用語辞典」p.294　新星出版社
>
>ヒープソート[heap sort]
>ヒープを再構成しながら、ヒープから最大値（または最小値）
>を取り出すことによって行う整列法。
>「情報処理用語辞典」p.300　新星出版社

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

> ソートの名前と機能との対応が覚えられません。
> 語呂合わせで覚えている方がいたら教えてほしいのですが。

　語呂あわせの本が出版されていましたよ。アルゴリズムと英語の意味から，
考えれば，覚えやすいと思います。トランプを１０枚用意して，手でやって
見て下さい。
　シェルは，貝殻で挟む，ヒープは山，バブルは泡が水の中を上がってくる，
イメージです。

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

　親の節の値が子の節の値より小さいヒープがある。このヒープへの挿入は，要
素を最後部に追加し，その要素が親よりも小さい間，親と子を交換することを繰
り返せばよい。次のヒープの * の位置に要素 7 を追加したとき，A の位置に来
る要素はどれか。

　　　　　　 　　　　(9)
　　　　　　　　　／　　＼
　　　　　　　　／　　　　＼
　　　　　　　／　　　　　　＼
　　　　　　(11)　　　　　　　(14)
　　　　　／　　＼　　　　　　／　＼
　　　 ／ 　 　　　＼ A　　／　 　 　＼
　　(24) 　 　 　　((25))　(19)　　　(28)
　　／＼　　　　／
　／　　＼　　／
(29)　　(34) *


　ア　7

　イ　11

　ウ　24

　エ　25

(解答例）

*に7を入れると、子が親より小さいと
入れ替えることから
（1）25と7を入れ替える　←　Aは7になる
（2）11と7を入れ替える　←　Aは11になる
（3）9と7を入れ替える　  ←　Aの11はかわらず
の処理を実行する。
よって、Aは11となる。


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

>条件を満たすようにヒープを完成させるには以下の１〜４の手順で進めます。
>
>１．＊に７を追加した状態
>　　　　　　　　　　(9)
>　　　　　　　　　／　　＼
>　　　　　　　　／　　　　＼
>　　　　　　　／　　　　　　＼
>　　　　　(11)　　　　　　　(14)
>　　　　／　　＼　　　　　　／　＼
>　　　／　　　　＼ A　　　／　　　＼
>　　(24)　　　　((25))　(19)　　　(28)
>　　／＼　　　　　／
>　／　　＼　　　／
>(29)　　(34)　7
>
>２．７と２５の交換
>　　　　　　　　　　(9)
>　　　　　　　　　／　　＼
>　　　　　　　　／　　　　＼
>　　　　　　　／　　　　　　＼
>　　　　　(11)　　　　　　　(14)
>　　　　／　　＼　　　　　　／　＼
>　　　／　　　　＼ A　　　／　　　＼
>　　(24)　　　　  (7)　(19)　　　(28)
>　　／＼　　　　　／
>　／　　＼　　　／
>(29)　　(34)　(25)
>
>３．１１と７の交換
>　　　　　　　　　　(9)
>　　　　　　　　　／　　＼
>　　　　　　　　／　　　　＼
>　　　　　　　／　　　　　　＼
>　　　　   (7)　　　　　　　(14)
>　　　　／　　＼　　　　　　／　＼
>　　　／　　　　＼ A　　　／　　　＼
>　　(24)　　　　  (11)　(19)　　　(28)
>　　／＼　　　　　／
>　／　　＼　　　／
>(29)　　(34)　(25)
>
>４．７と９の交換でヒーブ完成
>　　　　　　　　　　(7)
>　　　　　　　　　／　　＼
>　　　　　　　　／　　　　＼
>　　　　　　　／　　　　　　＼
>　　　　   (9)　　　　　　　(14)
>　　　　／　　＼　　　　　　／　＼
>　　　／　　　　＼ A　　　／　　　＼
>　　(24)　　　　  (11)　(19)　　　(28)
>　　／＼　　　　　／
>　／　　＼　　　／
>(29)　　(34)　(25)
>
>よってＡには１１がくる。

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