1.整列アルゴリズムとは
整列アルゴリズムとは、昇順または降順に並び替えることです。たとえば、以下が昇順に整列させたようすです。
45836 →34568
整列アルゴリズムには、いくつかの方法があります。
試験ではそれほど問われませんが、たまに問われる内容です。順に見ていきましょう。
2.選択ソート
過去問(H17秋SW午前問12)では、「未整列の並びに対して,最小のキー値をもつ要素と先頭の要素とを入れ換える。同様の操作を,未整列の並びの長さを一つずつ減らしながら繰り返す。」と述べられています。3.バブルソート(交換法)
過去問(H20春SW午前問11不正解選択肢)では、「隣り合う要素を比較して,大小の順が逆であれば,それらの要素を入れ替えるという操作を繰り返す。」と述べられています。簡単な例を述べます。小さい数字が上に来るように並べ替えます。一番下の2とその上の1を比べます。次に、1と4を比べます。1の方が小さいので入れ替えます。次に、1と3を比べ、小さい1を上にします。こうやって、一番上にはもっとも小さい数字が来ます。これを繰り返します。
では、以下をやってみましょう。6個の要素を持つ以下の配列があります。
a(6)={21,5,53,71,3,17}
右から左へのバブルソートによって、昇順に整列させます。
比較するのは、6つ目と5つ目、5つ目と4つ目、4つ目と3つ目・・・・2つ目と1つ目です。そして、小さい方に入れ替えます。1回目は以下のようになります。
右から左なので、17と3を比較し、3の方が小さいのでそのままです。次に、3と71を比較し、3の方が小さいので入れ替えます。
このようにすると、最後は
3 21 5 53 71 17 です。
2回目→ 3 5 21 17 53 71
3回目→ 3 5 17 21 53 71
となり、3回で整列します。しかし、実際にはもう少し時間がかかる場合もあれば、最初から整列している場合には、1回もやらずに整列する場合もあります。最長は、5回(n-1)です。
では、これをアルゴリズムにしてみましょう。1回目の操作だけに着目します。
①a[6](=17) とa[5](=3)を比較し、a[5]の方が大きければ、a[5]とa[6]を入れ替えます。
②a[5](=3) とa[4](=71)を比較し、a[4]の方が大きければ、a[4]とa[5]を入れ替えます。
③・・・
⑤a[2](=3) とa[1](=21)を比較し、a[1]の方が大きければ、a[1]とa[2]を入れ替えます。
なんとなく、アルゴリズムが見えてきましたね。
・ループ条件:j=6(初期値)、j>=2(継続条件)、j--(増分の式)
・判断:a[j-1]>a[j]
・処理(Yesの場合):a[j-1]とa[j]を入れ替え。
ただし、a[j-1]とa[j]を入れ替えるのは、人間には簡単ですが、プログラムでは工夫が必要です。
・a[j-1]→w (値をwに退避)
・a[j]→a[j-1]
・w→a[j]
この処理を、何回も繰り返すだけです。
では、何回繰り返すでしょうか。それは、要素数をNとすると、最長はN-1回です。1回処理することに、一番小さい数字が一番左に行きます。N-1回繰り返せば、必ず整列します。
また、2回目、3回目と繰り返す際に、上記の処理は1回ずつ少なくて済みます。なぜなら、1番小さい数は一番左にすでに配置されているからです。
なので、アルゴリズムとしては、以下のようになります。※a[j-1]とa[j]を入れ替えは簡略化されています。
過去問(H25秋AP午前問9)を見てみましょう。
問9 未整列の配列α[i] (i=1,2, …,n)を,流れ図で示すアルゴリズムによって昇順に整列する。n=6でa[1]~a[6]の値がそれぞれ, 21,5,53,71,3,17の場合,流れ図において,a[j-1]とa[j]の値の入替えは何回行われるか。 ア 3 イ 6 ウ 8 エ 15 |
↓
↓
↓
↓
バブルソートを利用しています。【正解】ウ
4.マージソート
過去問(H26秋AP午後問3)では、マージソートに関して、「マージソートは,整列(ソート)したいデータ(要素)列を,細かく分割した後に,併合(マージ)を繰り返して全体を整列する方法である」と述べています。過去問(H26秋AP午後問3)に具体的なイメージがあるので、みてみましょう。
問3 マージソートに関する次の記述を読んで,設問1~3に答えよ。 マージソートは,整列(ソート)したいデータ(要素)列を,細かく分割した後に,併合(マージ)を繰り返して全体を整列する方法である。 ここでは,それぞれの要素数が1になるまでデータ列の分割を繰り返し,分割されたデータ列を昇順に並ぶように併合していくアルゴリズムを考える。例として,要素数が8の場合のアルゴリズムの流れを図1に示す。 (後半略) |
分割したあと、併合(マージ)するからマージソートですね!
では、過去問を見てみよう!
■H26秋AP
問6 データ列が整列の過程で図のように上から下に推移する整列方法はどれか。ここで図中のデータ列申の縦の区切り線は,その左右でデータ列が分割されていることを示す。
ア クイックソート イ シェルソート
ウ ヒープソート エ マージソート
【正解】エ
5.挿入ソート
過去問(H17秋SW午前問12)では、「未整列要素の並びの先頭の要素を取り出し,その要素を整列済みの要素の申の正しい位置に挿入する。」と述べられています。6.シェルソート
過去問(H20春SW午前問11不正解選択肢)では、「ある一定間隔おきに取り出した要素から成る部分列をそれぞれ整列し,更に間隔を詰めて同様の操作を行い,間隔が1になるまでこれを繰り返す。」と述べられています。7.クイックソート
過去問(H20春SW午前問11不正解選択肢)では、「中間的な基準値を決めて,それよりも大きな値を集めた区分と小さな値を集めた区分に要素を振り分ける。次に,それぞれの区分の中で同様な処理を繰り返す。」と述べられています。8.ヒープソート
まず、ヒープとはなんでしょう。過去問(平成17年春FE午後問4)では、以下の解説があります。
ヒープとは,図のように,各節の値が自分の子の節の値以上になっている2分木である。 |
かなり簡略化していますが、イメージをつかんでいただきたいと思います。
まず、(ⅰ)で、3412を2分木にします。
(ⅱ)一番大きな値である4が一番上に来るように入れ替えます。
(ⅲ)最大値の4を取り出します。
(ⅳ)以降、このような最大値を取り出すことを繰り返します。
■過去問平成28年秋期 午前 問6
問6 ヒープソートの説明として,適切なものはどれか。 ア ある間隔あきに取り出した要素から成る部分列をそれぞれ整列し,更に間隔を詰めて同様の操作を行い,間隔が1になるまでこれを繰り返す。 イ 中間的な基準値を決めて,それよりも大きな値を集めた区分と,小さな値を集めた区分に要素を振り分ける。次に,それぞれの区分の中で同様な処理を繰り返す。 ウ 隣り合う要素を比較して,大小の順が逆であれば,それらの要素を入れ替えるという操作を繰り返す。 エ 未整列の部分を順序木にし,そこから最小値を取り出して整列済の部分に移す。この操作を繰り返して,未整列の部分を縮めていく。 |
↓
↓
↓
↓
アはシェルソート
イはクイックソート
ウはバブルソート
問11 データの整列方法に関する記述のうち,適切なものはどれか。 ア クイックソートでは,ある一定間隔おきに取り出した要素から成る部分列をそれぞれ整列し,更に間隔を詰めて同様の操作を行い,間隔が1になるまでこれを繰り返す。 イ シェルソートでは,隣り合う要素を比較して,大小の順が逆であれば,それらの要素を入れ替えるという操作を繰り返す。 ウ バブルソートでは,中間的な基準値を決めて,それよりも大きな値を集めた区分と小さな値を集めた区分に要素を振り分ける。次に,それぞれの区分の中で同様な処理を繰り返す。 エ ヒープソートでは,未整列の部分を順序木に構成し,そこから最大値又は最小値を取り出して既整列の部分に移す。この操作を繰り返して,未整列部分を縮めていく。 |
↓
↓
↓
↓
アはシェルソート
イはバブルソート
ウはクイックソート正解は、エです。 平成17年春期 FE 午後 問4
問4 次のプログラムの説明及びプログラムを読んで,設問1~3に答えよ。 〔プログラムの説明〕 副プログラムHeapSortは,配列に格納されている整数値をヒープソートで昇順に整列するプログラムである。 (1)整列するNum個(Num≧2)の整数値は,大域変数の配列A[1],A[2],・・・,A[Num]に格納されている。 (2)ヒープソートは,2分木を用いてデータを整列する。2分木を配列で表現するには,ある節がA[i]に対応するとき,その左側の子の節をA[2×i]に,右側の子の節をA[2×i+1]に対応させる。図では,丸が節を,丸中の数字が節の値を示し,実際に値が格納されている配列の要素を丸の脇に示している。 (3)ヒープとは,図のように,各節の値が自分の子の節の値以上になっている2分木である。 (4)整列の手順は,次のとおりである。 ① 配列Aの中の,A[1],A[2],・・・,A[Num]を整列対象とする。 ② 整列対象の各要素が,(2)で述べたような2分木を表現しているものとして,要素の値を入れ換えてヒープを作る。その結果,木の根(A[1])には整列対象の要素の最大値が入る。 ③ 木の根(A[1])の値と,木の最後の節(整列対象の最後の要素に対応する節)の値とを交換する。 ④ 木の最後の節を2分木から取り除く(整列対象の要素を一つ減らす)。 ⑤ ④の結果が,木の根だけになるまで,②~④の処理を繰り返す。 (5)ヒープを作り直す手順は,次のとおりである。 ① 木の根を親の節とする。 ② 子の節がなければ終了する。 ③ 二つの子の節のうち値が大きい方と親の節の値を比較し,親の節の方が小さいときは,値を交換する。親の節の値が子の節の値以上のときは,何もしないで終了する。 ④ 値を交換した子の節を根とする部分木に対して,①~③の処理を繰り返す。 |
設問1 プログラム中の[ ]に入れる正しい答えを,解答群の中から選べ。 aに関する解答群 ア L ← Top ウ L ← Top × 2 イ L ← Top + 1 エ L ← Top × 2 + 1 bに関する解答群 ア L ≦ Last ウ R ≦ Last - 1 イ L < Last エ R ≦ Last - 2 |
a ウ
b ア です。
設問2 次の記述中の[ ]に入れる正しい答えを,解答群の中から選べ。 図のヒープを用いて,〔プログラムの説明〕の(4)の③,④を1回だけ実行して,②が終了したとき,最初A[10]に入っていた値12が格納されている配列要素の添字は[ c ]である。また,それまでに節の値を交換した回数は[ d ]である。 解答群 ア 2 イ 3 ウ 4 エ 5 オ 6 カ 7 キ 8 ク 9 |
c キ
d ウ です。
設問3 最初にヒ―プを作成する副プログラムInitHeapはMakeHeapを使って作る ことができる。次のプログラム中の[ ]に入れる正しい答えを,解答群 の中から選べ。 解答群 ア Idx: 1,Idx ≦ Last,2 イ Idx: 1,Idx ≦ Last ÷ 2,1 ウ Idx: Last,Idx ≧ 1,-2 エ Idx: Last ÷ 2,Idx ≧ 1,-1 |