2014年 秋期 応用情報技術者試験 問3

マージソート

マージソートは、整列（ソート）したいデータ（要素）列を、細かく分割した後に、併合（マージ）を繰り返して全体を整列する方法である。

ここでは、それぞれの要素数が1になるまでデータ列の分割を繰り返し、分割されたデータ列を昇順に並ぶように併合していくアルゴリズムを考える。例として、要素数が8の場合のアルゴリズムの流れを図1に示す。

<div class="merge-phase">
  <div class="level">
    <div class="array">[4][6]</div>
    <div class="array">[3][8]</div>
    <div class="array">[2][7]</div>
    <div class="array">[1][5]</div>
  </div>
  <div class="level">
    <div class="array">[3][4][6][8]</div>
    <div class="array">[1][2][5][7]</div>
  </div>
  <div class="level">
    <div class="array">[1][2][3][4][5][6][7][8]</div>
  </div>
  <div class="phase-label">併合</div>
</div>

再帰呼出しを使って記述したマージソートのアルゴリズムを図2に示す。

図2のアルゴリズムを連結リストに対して実行するプログラムを考える。ここでは、整列対象のデータとして正の整数を考える。連結リストは、複数のセルによって構成される。セルは、正の整数値を示すメンバvalueと、次のセルへのポインタを示すメンバnextによって構成される。連結リストの最後のセルのnextの値は、NULLである。連結リストのデータ構造を図3に示す。

【連結リストの分割】

図2中の②の処理を行う関数divideを考える。関数divideは、連結リストの先頭へのポインタ変数listを引数とし、分割後の後半の連結リストの先頭へのポインタを戻り値とする。連結リストの分割前後のイメージを図4に示す。

<div class="after">
  <div class="label">分割後</div>
  <div class="list-pointer">list →</div>
  <div class="linked-list">
    [44] → [10] → [16] /
  </div>
  <div class="return-value">関数divideの戻り値</div>
  <div class="linked-list">
    [23] → [8] → [35] /
  </div>
</div>

連結リストをセルの個数がほぼ同じになるように分割するために、ポインタ変数を二つ用意し、一方が一つ進むごとに、他方を二つずつ進める。後者のポインタが連結リストの終わりに達するまでこの処理を繰り返すと、前者のポインタは連結リストのほぼ中央のセルを指す。この方法を利用した関数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に示す。

<div class="step">
  <div class="step-label">②</div>
  <div class="pointers">
    <div>a → [10] → [16] → [44] /</div>
    <div>b → [23] → [35] /</div>
  </div>
  <div>head → [-] → [8] → [23] → [35] /</div>
</div>

<div class="step">
  <div class="step-label">③</div>
  <div class="pointers">
    <div>a → [16] → [44] /</div>
    <div>b → [23] → [35] /</div>
  </div>
  <div>head → [-] → [8] → [10] → [16] → [44] /</div>
  <div class="continue">⋮</div>
</div>

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