応用情報技術者試験 過去問 2014年（平成26年） 秋期 午後 問3
マージソート
マージソートは、整列（ソート）したいデータ（要素）列を、細かく分割した後に、併合（マージ）を繰り返して全体を整列する方法である。
ここでは、それぞれの要素数が1になるまでデータ列の分割を繰り返し、分割されたデータ列を昇順に並ぶように併合していくアルゴリズムを考える。例として、要素数が8の場合のアルゴリズムの流れを図1に示す。
再帰呼出しを使って記述したマージソートのアルゴリズムを図2に示す。
- 与えられたデータ列の要素数が1以下であれば、整列済みのデータ列とし、呼出し元に処理を戻す。要素数が2以上であれば、(2)に続く。
- データ列を、要素数がほぼ同じになるよう前半と後半のデータ列に分割する。
- 前半と後半のデータ列に対し、それぞれマージソートのアルゴリズムを再帰的に呼び出す。
- 前半と後半の二つのマージソート済みデータ列を、要素が昇順に並ぶよう一つのデータ列に併合する。
図2のアルゴリズムを連結リストに対して実行するプログラムを考える。ここでは、整列対象のデータとして正の整数を考える。連結リストは、複数のセルによって構成される。セルは、正の整数値を示すメンバvalueと、次のセルへのポインタを示すメンバnextによって構成される。連結リストの最後のセルのnextの値は、NULLである。連結リストのデータ構造を図3に示す。
【連結リストの分割】
図2中の②の処理を行う関数divideを考える。関数divideは、連結リストの先頭へのポインタ変数listを引数とし、分割後の後半の連結リストの先頭へのポインタを戻り値とする。連結リストの分割前後のイメージを図4に示す。
連結リストをセルの個数がほぼ同じになるように分割するために、ポインタ変数を二つ用意し、一方が一つ進むごとに、他方を二つずつ進める。後者のポインタが連結リストの終わりに達するまでこの処理を繰り返すと、前者のポインタは連結リストのほぼ中央のセルを指す。この方法を利用した関数divideのプログラムを図5に示す。
以下、連結リストのセルを指すポインタ変数をaとするとき、aが指すセルのメンバvalueをa->valueと表記する。
function divide( list )
a ← list // aはセルへのポインタ
b ← a->next // bはセルへのポインタ
if ( b が NULL と等しくない )
b ← b->next
endif
while ( ア ) // 連結リストの終わりまで繰り返す
a ← a->next
b ← b->next
if ( b が NULL と等しくない )
イ
endif
endwhile
←----------------α
p ← a->next // pはセルへのポインタ
ウ ← NULL
return p
endfunction
【連結リストの併合】
図2中の④の処理を行う関数mergeを考える。関数mergeは、二つの連結リストの先頭へのポインタ変数aとbを引数とし、併合後の連結リストの先頭へのポインタを戻り値とする。併合処理を行う際には、ダミーのセルを用意し（そのセルへのポインタをheadとする）、この後ろに併合後の連結リストを構成する。aとbが指すセルの値を比較しながら、値が小さい順に並ぶよう処理を進める。連結リストの併合の流れを図6（処理は、①、②、③、…と続く）に、関数mergeのプログラムを図7に示す。
function merge( a, b ) // a, bは併合対象の連結リストの先頭へのポインタ
ダミーのセルを用意する
head ← ダミーのセルへのポインタ
p ← head
while ( エ , かつ, b が NULL と等しくない )
if ( a->value が b->value 以下である )
p->next ← a
p ← a
a ← a->next
else
p->next ← b
p ← b
b ← b->next
endif
endwhile
if ( オ ) // 要素が残っている連結リストを連結する
p->next ← b
else
p->next ← a
endif
return カ
endfunction