プログラミング通論 コード穴埋め問題集

期末試験範囲（第8回〜第14回）の実装を全部書けるようにするための問題集。コードの空欄 ___ を埋めて、解答コールアウトで答え合わせをする。

使い方

1. 紙に（または頭の中で）空欄を埋めてみる
2. [!note]- 解答 をクリックして答え合わせ
3. [!tip]- 解説 で「なぜそう書くのか」を確認
4. 書けなかった問題は翌日にもう一度

共通の型定義（全問共通）

以下の定義は授業ノートで毎回登場するもの。ここで確認しておく。

/* リストのノード */
struct node {
    elementtype element;   /* 保持するデータ */
    struct node *next;     /* 次のノードへのポインタ */
};
 
/* ソート対象のレコード */
typedef struct {
    keytype key;           /* ソートの基準となるキー */
    elementtype element;   /* 付随するデータ */
} recordtype;
 
/* 2つのレコードを入れ替える（ソートで多用） */
void swap( recordtype *x, recordtype *y ){
    recordtype tmp;
    tmp = *x;
    *x = *y;
    *y = tmp;
}

添字の約束

• リストは head というデータを持たない先頭ノードを使う
• ソートの配列は a[0] を使わず a[1]〜a[n] で扱う（選択・挿入・バブル・ヒープ・分布数え上げ）
• ただしクイックソート2・マージソート・探索は a[0] から使う

---

Part 1: リスト構造とその応用（第8・9回）

問1: リストの初期化 initlist

空のリスト（head のみ）を作る関数。head はデータを持たないノード。

struct node *initlist ( void ) {
    struct node *n;
    n = ___①___malloc ( sizeof ( struct node ) );   /* ノード用メモリ確保 */
    n -> next = ___②___NULL;                      /* 次はまだ無い */
    return n;
}

解答

①: malloc　②: NULL

struct node *initlist ( void ) {
    struct node *n;
    n = (struct node *) malloc ( sizeof ( struct node ) );
    n -> next = NULL;
    return n;
}

解説

malloc が必要なのは、関数内で struct node n; と宣言するとローカル変数になり、関数が終わった瞬間に消えてしまうから。

malloc で確保した領域は解放するまで残り続ける。だからリストのような「関数をまたいで生き残る構造」には malloc が必須。

head はデータを持たない番兵ノード。next だけが意味を持つ。

問2: リストへの挿入 insert

ノード p の直後に、値 x を持つノードを挿入する。

void  insert ( struct node *p,  elementtype  x ) {
    struct node *n;
    n = ( struct node * ) malloc ( sizeof ( struct node ) );
    n -> element = x;
    n -> next = ___①___p->next;     /* 元のリストの続きを n につなぐ */
    ___②___p->next = n;             /* p の次を n に張り替える */
}

解答

①: p -> next　②: p -> next

void  insert ( struct node *p,  elementtype  x ) {
    struct node *n;
    n = ( struct node * ) malloc ( sizeof ( struct node ) );
    n -> element = x;
    n -> next = p -> next;   /* ① */
    p -> next = n;           /* ② */
}

解説

①と②の順番が命。

①で「n の次」に「p の元々の次」を退避しておいてから、②で「p の次」を n に張り替える。

逆に②を先にやると p 以降のリストが迷子になり、①で参照できなくなる。まず後ろを確保してから、前を書き換える。これがポインタ操作の鉄則。

問3: リストからの削除 delete

p が指すノードの次のノードを削除する。

void delete ( struct node *p ) {
    if ( ___①___p->next != NULL ) {
        p -> next = ___②___p->next->next;
    }
}

解答

①: p -> next　②: p -> next -> next

void delete ( struct node *p ) {
    if ( p -> next != NULL ) {
        p -> next = p -> next -> next;
    }
}

解説

引数は「削除したいノード」ではなく「その直前のノード」。単方向リストは前のノードからしか次を書き換えられないから。

削除対象は p->next。その次の p->next->next を p の次に繋ぎ直せば、削除対象はリストの連鎖から外れる。

ここでは free() していない。メモリ領域としては残るが、リンクから外れればリストとしては消えたのと同じ。

---

問4: リストでスタック push / pop

リストの head をスタックのトップとして使う。typedef struct node *stack; とする。

void push ( stack s, elementtype x ) {
    ___①___insert ( s, x );        /* 先頭に挿入 = リストの insert を再利用 */
}
 
elementtype pop ( stack s ) {
    elementtype retval;
    if ( ___②___stackempty ( s ) ) {   /* 空チェック */
        printf ( "underflow\n" );
        exit(1);
    } else {
        retval = s->next->element___③___;    /* 先頭ノードのデータを取り出す */
        ___④___delete ( s );       /* 先頭ノードを削除 */
        return retval;
    }
}

解答

①: insert　②: stackempty　③: s -> next -> element　④: delete

void push ( stack s, elementtype x ) {
    insert ( s, x );
}
 
elementtype pop ( stack s ) {
    elementtype retval;
    if ( stackempty ( s ) ) {
        printf ( "underflow\n" );
        exit(1);
    } else {
        retval = s -> next -> element;
        delete ( s );
        return retval;
    }
}

解説

push は head の直後に挿入、pop は head の直後を取り出して削除。つまりリストの insert/delete をそのまま使うだけ。

head の次に挿入・削除すれば LIFO（後入れ先出し）になる。head への操作は常に O(1)。

stackempty は s -> next == NULL で判定。pop で空のときは underflow としてエラー終了する。

問5: リストでキュー enqueue / dequeue

struct queue { link front, rear; } で、front は head、rear は末尾を指す。

void enqueue ( struct queue *q, elementtype x ) {
    ___①___insert ( q -> rear, x );   /* 末尾に挿入 */
    q -> rear = q->rear->next___②___;         /* rear を新しい末尾へ更新 */
}
 
elementtype dequeue ( struct queue *q ) {
    elementtype retval;
    if ( queueempty ( *q ) ) {
        printf ( "underflow\n" ); exit(1);
    } else {
        retval = q->front->next->element___③___;        /* 先頭ノードのデータ */
        ___④___delete ( q -> front );  /* 先頭を削除 */
        if ( queueempty ( *q ) ) {
            q -> rear = q -> front;   /* 空になったら rear も head に戻す */
        }
        return retval;
    }
}

解答

①: insert　②: q -> rear -> next　③: q -> front -> next -> element　④: delete

void enqueue ( struct queue *q, elementtype x ) {
    insert ( q -> rear, x );
    q -> rear = q -> rear -> next;
}
 
elementtype dequeue ( struct queue *q ) {
    elementtype retval;
    if ( queueempty ( *q ) ) {
        printf ( "underflow\n" ); exit(1);
    } else {
        retval = q -> front -> next -> element;
        delete ( q -> front );
        if ( queueempty ( *q ) ) {
            q -> rear = q -> front;
        }
        return retval;
    }
}

解説

キューは FIFO（先入れ先出し）。追加は rear（末尾）、取り出しは front（先頭）。

enqueue は insert で末尾の次に追加し、rear を 1 つ進める。rear は常に「最後のノード」を指すように保つ。

dequeue で最後の 1 個を削除すると、rear はもう存在しないノードを指したままになる。そこで queueempty を再チェックして rear を front（head）に巻き戻す。この一手を忘れると rear が迷子になる。

問6: リストの逆転 reverse2（リンクつなぎ替え）

ノードを複製せず、next リンクを逆向きにつなぎ替えて逆順にする。

link reverse2 ( link p ) {
    link head, oldp, keep;
    head = p; oldp = ___①___;   /* 1つ前のノード（最初は無い） */
    p = p -> next;              /* 注目ノードへ */
    while ( p != NULL ) {
        keep = oldp;
        oldp = p;
        p = p -> next;
        oldp -> next = ___②___;   /* 注目ノードの次を1つ前へ向ける */
    }
    head -> next = ___③___;       /* head の次に最後尾を繋ぐ */
    return head;
}

解答

①: NULL　②: keep　③: oldp

link reverse2 ( link p ) {
    link head, oldp, keep;
    head = p; oldp = NULL; p = p -> next;
    while ( p != NULL ) {
        keep = oldp;
        oldp = p;
        p = p -> next;
        oldp -> next = keep;
    }
    head -> next = oldp;
    return head;
}

解説

3つのポインタを「keep → oldp → p」と 1 つずつ右にずらしながら、oldp->next を 1 つ前の keep に向ける。

注目ノードの次を書き換えると元の次を辿れなくなるので、書き換える前に p で次を確保しておく。これが keep/oldp/p が3本必要な理由。

ループ終了時、oldp は最後尾、p は NULL。head の次に oldp を繋げば逆転完了。

---

Part 2: ソート（第11〜14回）

問7: 選択ソート selection_sort

「残りの中から最小値を探して、先頭に持ってくる」を繰り返す。配列は a[1]〜a[n]。

void selection_sort( recordtype a[], int n ){
    int i, j, minindex;
    for( i=1; i<n; i++ ){
        minindex = i;
        for( j=___①___1; j <= n; j++ ){        /* 未整列部分を走査 */
            if( a[j].key < a[minindex].key___②___ ){          /* より小さい値を見つけた */
                minindex = j;
            }
        }
        ___③___swap ( &a[minindex], &a[i] );       /* 最小値を先頭へ */
    }
}

解答

①: i+1　②: a[minindex].key　③: swap

void selection_sort( recordtype a[], int n ){
    int i, j, minindex;
    for( i=1; i<n; i++ ){
        minindex = i;
        for( j=i+1; j <= n; j++ ){
            if( a[j].key < a[minindex].key ){
                minindex = j;
            }
        }
        swap( &a[minindex], &a[i] );
    }
}

解説

外側の i が「ここを埋める場所」、内側のループが「i 以降の最小値を探す」。

最小値を更新するたびに swap するのではなく、minindex に場所だけ記録して、探し終わったら 1 回だけ swap。ここがポイント。

比較は n(n-1)/2 回で O(n²)。移動は 1 要素あたり高々 1 回なので、レコードが大きい（コピーが重い）場合に意外と有利。

問8: 挿入ソート insertion_sort

先頭から順に「整列済み部分の正しい位置に、1 枚ずつ挿入」していく。番兵に INT_MIN を使う。

void insertion_sort( recordtype a[], int n ){
    int i, j; recordtype v;
    a[0].key = INT_MIN___①___;        /* 番兵：key の最小値 */
    for( i=2; i<=n; i++ ){
        v = a[i]; j = i;
        while( ___②___a[j-1].key > v.key ){   /* 1つ前が自分より大きい間 */
            a[j] = ___③___a[j-1];         /* 1つ前を後ろにずらす */
            j--;
        }
        ___④___a[j] = v;                /* 空いた場所に挿入 */
    }
}

解答

①: INT_MIN　②: a[j-1].key　③: a[j-1]　④: a[j]

void insertion_sort( recordtype a[], int n ){
    int i, j; recordtype v;
    a[0].key = INT_MIN;
    for( i=2; i<=n; i++ ){
        v = a[i]; j = i;
        while( a[j-1].key > v.key ){
            a[j] = a[j-1];
            j--;
        }
        a[j] = v;
    }
}

解説

操作は2段階。操作B（外側）で i を 1 つずつ進め、操作A（内側）で a[i] を正しい位置に挿入する。

内側の while では「1つ前を後ろにずらす」だけ。ずらし終わって空いた場所に v を置く。

a[0] に INT_MIN（-∞）を置くのが番兵。j が 0 に達しても必ず a[0].key > v.key が偽になり、配列の先頭チェック（j>=1）を省略できる。これが番兵の効能。

ほぼ整列済みなら while はすぐ終わり O(n)。平均・最悪は O(n²)。

問9: バブルソート bubble_sort

右端から隣同士を比較し、小さい方を左へ運ぶ。泡（バブル）が浮かぶように見えるのが名前の由来。

void bubble_sort( recordtype a[], int n ){
    int i, j;
    for( i=1; i<n; i++ ){
        for( j=n; j>=1___①___; j-- ){        /* 右端から左へ */
            if( a[j].key < a[j-1].key___②___ ){        /* 隣同士を比較 */
                ___③___swap ( &a[j], &a[j-1] );  /* 小さい方を前へ */
            }
        }
    }
}

解答

①: i+1　②: a[j-1].key　③: swap

void bubble_sort( recordtype a[], int n ){
    int i, j;
    for( i=1; i<n; i++ ){
        for( j=n; j>=i+1; j-- ){
            if( a[j].key < a[j-1].key ){
                swap( &a[j], &a[j-1] );
            }
        }
    }
}

解説

1 周ごとに最小値が左端に確定する。外側の i が「確定済みの数」を表し、内側は右端から i+1 まで。

比較回数は常に n(n-1)/2 で O(n²)。

交換回数はデータの初期状態で変わる：最良（整列済み）0 回、最悪 n(n-1)/2 回。計算量が初期状態に依存するのが特徴。

---

問10: シェルソート shell_sort

「間隔 h だけ離れた要素同士で挿入ソート」を、h を縮めながら繰り返す。h は 3h+1 で成長させる。

void shellsort( recordtype a[], int n ){
    int i, j, h; recordtype v;
    for( h=1; h*3+1 <= n/9; h = h*3+1 );   /* 間隔hの初期値を決める */
    for( ; h > 0; h /= 3 ){                /* hを3で割って狭める */
        for( i = h+1; i <= n; i++ ){
            v = a[i]; j = i;
            while( ___①___ && ___②___ > v.key ){  /* h個前と比較 */
                a[j] = a[j-h];             /* h個左の要素を右へずらす */
                j -= h;
            }
            a[j] = v;
        }
    }
}

解答

①: j > h　②: a[j-h].key

void shellsort( recordtype a[], int n ){
    int i, j, h; recordtype v;
    for( h=1; h*3+1 <= n/9; h = h*3+1 );
    for( ; h > 0; h /= 3 ){
        for( i = h+1; i <= n; i++ ){
            v = a[i]; j = i;
            while( j > h && a[j-h].key > v.key ){
                a[j] = a[j-h];
                j -= h;
            }
            a[j] = v;
        }
    }
}

解説

中身は挿入ソートそっくり。違うのは「1つ前」ではなく「h 個前」と比較・ずらす点だけ。

挿入ソートの j>=1 の代わりに j > h が番兵代わりの条件。a[0] に何も置かなくても範囲チェックできる。

h を 1 まで縮めると普通の挿入ソートになる。でも「遠くの要素を先に大きく動かして」から縮めるので、比較回数が大幅に減る。

計算量は O(n^3/2) 程度。O(n²) より明確に速い。

問11: クイックソート quicksort + partition（Hoare の方法）

pivot を境に「小さいグループ」「大きいグループ」に分ける分割統治法。左端を pivot にし、i を左から、j を右から走査する。

void quicksort( recordtype a[], int l, int r ){
    int i;
    if ( l < r ){
        i = ___①___partition ( a, l, r );   /* pivot の位置を決める */
        quicksort( a, l, i-1 );     /* 左部分列を再帰 */
        quicksort( a, i+1, r );     /* 右部分列を再帰 */
    }
}
 
int partition( recordtype a[], int l, int r ){
    int i, j; recordtype v;
    v = a[l]; i = l; j = r+1___②___;    /* j は右端の1つ外から */
    do {
        do { i++; } while( a[i].key < v.key );   /* pivotより大きい値を探す */
        do { j--; } while( a[j].key > v.key );   /* pivotより小さい値を探す */
        if ( i < j ){
            ___③___swap ( &a[i], &a[j] );           /* 交差していなければ入れ替え */
        }
    } while ( ___④___j<i );                        /* 交差するまで繰り返す */
    a[l] = a[j]; a[j] = v;                       /* pivot を正しい位置へ */
    return ___⑤___j;
}

解答

①: partition　②: r + 1　③: swap　④: j > i　⑤: j

void quicksort( recordtype a[], int l, int r ){
    int i;
    if ( l < r ){
        i = partition( a, l, r );
        quicksort( a, l, i-1 );
        quicksort( a, i+1, r );
    }
}
 
int partition( recordtype a[], int l, int r ){
    int i, j; recordtype v;
    v = a[l]; i = l; j = r + 1;
    do {
        do { i++; } while( a[i].key < v.key );
        do { j--; } while( a[j].key > v.key );
        if ( i < j ){
            swap( &a[i], &a[j] );
        }
    } while ( j > i );
    a[l] = a[j]; a[j] = v;
    return j;
}

解説

partition が「pivot より小さいものは左、大きいものは右」に分け、pivot の最終位置 j を返す。quicksort 本体はその左右を再帰でソートするだけ。

i は左から「pivot より大きい値」を、j は右から「pivot より小さい値」を探す。見つけたら入れ替え。i と j が交差したら終了。

j が「pivot より小さい値の右端」になっているので、最後に pivot を a[j] と入れ替える。j = r+1 なのは do-while で最初に j— するため（意図的に +1）。

注意点：配列末尾に範囲チェックや番兵が無い。pivot が極端に小さい/大きいと a[r+1] や a[l-1] を読む危険がある。

平均 O(n log n)、最悪 O(n²)（pivot が偏る時）。ランダムに pivot を選ぶと最悪を避けやすい。

問12: クイックソート2 quicksort2（Lomuto の方法）

a[0] からデータが入っている配列用。pivot を乱数で選び、pivot より小さいものを左に詰めていく。

void quicksort2( recordtype a[], int n ){
    int i, last;
    if( n <= 1 ) return;                        /* 終端条件 */
    ___①___swap ( &a[0], &a[ rand() % n ] );       /* pivot を乱数で選び先頭へ */
    last = 0;                                   /* pivotより小さい値の右端 */
    for( i = 1; i < n; i++ ){
        if ( a[i].key < a[0].key ){
            ___②___swap ( &a[++last], &a[i] );     /* last の次に詰めて入れ替え */
        }
    }
    ___①___swap ( &a[0], &a[last] );               /* pivot を正しい位置へ */
    quicksort2( a, last );                      /* 左部分列 */
    quicksort2( ___③___a+last+1 , n - last - 1 );      /* 右部分列 */
}

解答

①: swap　②: swap　③: a + last + 1

void quicksort2( recordtype a[], int n ){
    int i, last;
    if( n <= 1 ) return;
    swap( &a[0], &a[ rand() % n ] );
    last = 0;
    for( i = 1; i < n; i++ ){
        if ( a[i].key < a[0].key ){
            swap( &a[++last], &a[i] );
        }
    }
    swap( &a[0], &a[last] );
    quicksort2( a, last );
    quicksort2( a + last + 1, n - last - 1 );
}

解説

Hoare と違って「pivot より小さい値を先頭側に順に詰める」方式。配列末尾まで探索するので番兵が不要。

last が「pivot より小さい値の右端」を表し、小さい値を見つけるたびに ++last と入れ替える。最後に pivot を a[last] と入れ替えれば、左が小さいグループ、右が大きいグループに分かれる。

右部分列はポインタ a + last + 1 で「pivot の後ろから」始まる配列として再帰する。

rand() % n で pivot をランダムに選ぶので、整列済みデータでも最悪ケースになりにくい。

---

問13: ヒープソート pushdown + heapsort

ヒープ（親 ≥ 子 の完全二分木）を作り、根（最大値）を取り出して末尾に置くのを繰り返す。

void pushdown( recordtype a[], int first, int last ){
    int r = first, k = 2 * r;        /* r=親, k=左の子 */
    while( k <= last ){
        if( k < last && ___①___ ){  /* 右の子の方が大きいなら */
            k++;                     /* 大きい方の子を選択 */
        }
        if( a[r].key >= a[k].key ){
            break;                   /* ヒープ条件OK → 終了 */
        }
        ___②___ ( &a[r], &a[k] );   /* 親 < 子 → 入れ替え */
        r = k; k = ___③___;         /* さらに下のノードへ */
    }
}
 
void heapsort( recordtype a[], int n ){
    int i;
    for( i = n/2; i >= 1; i-- ){     /* ボトムアップにヒープ化 */
        ___④___ ( a, i, n );
    }
    for( i = n; i >= 2; i-- ){
        ___②___ ( &a[1], &a[i] );   /* 最大値（根）を末尾へ */
        ___④___ ( a, 1, i-1 );      /* 縮んだヒープを再構築 */
    }
}

解答

①: a[k].key < a[k+1].key　②: swap　③: 2 * r　④: pushdown

void pushdown( recordtype a[], int first, int last ){
    int r = first, k = 2 * r;
    while( k <= last ){
        if( k < last && a[k].key < a[k+1].key ){
            k++;
        }
        if( a[r].key >= a[k].key ){
            break;
        }
        swap( &a[r], &a[k] );
        r = k; k = 2 * r;
    }
}
 
void heapsort( recordtype a[], int n ){
    int i;
    for( i = n/2; i >= 1; i-- ){
        pushdown( a, i, n );
    }
    for( i = n; i >= 2; i-- ){
        swap( &a[1], &a[i] );
        pushdown( a, 1, i-1 );
    }
}

解説

配列の添字と木の位置の対応が全て。親 i の子は 2i と 2i+1、子 i の親は ⌊i/2⌋。

pushdown は「親を子と比べ、大きい方の子と入れ替えながら下げる」操作。子が両方居て右が大きければ k++ で右の子を選ぶ。

ヒープ化は n/2 から 1 へ（最後のノードの親から）ボトムアップに行う。下の部分木から整えると、上の段に来た時点で下はもうヒープ。

ヒープ化が O(n)、取り出し+再構築が O(log n) × n 回で、全体 O(n log n)。作業用配列が要らない（in-place）のが強み。

問14: 分布数え上げソート distribution_counting

比較を一切せず、キーの「度数分布」と「累積度数分布」を使って整列する。キーの範囲 m が既知であることが前提。

void distribution_counting( recordtype a[], int n ){
    int i, j, count[m];
    recordtype b[n+1];
    for( j = 0; j < m; j++ ){ ___①___; }        /* 度数分布を初期化 */
    for( i = 1; i <= n; i++ ){ ___②___; }        /* 度数分布を作成 */
    for( j = 1; j < m; j++ ){ ___③___; }        /* 累積度数分布に変換 */
    for( i = n; i >= 1; i-- ){
        b[ ___④___ ] = a[i];                    /* 累積数が格納場所 */
        count[a[i].key]--;                       /* 同じ値対策で減らす */
    }
    for( i = 1; i <= n; i++){ a[i] = b[i]; }     /* 元の配列に戻す */
}

解答

①: count[j] = 0　②: count[a[i].key]++　③: count[j] += count[j-1]　④: count[a[i].key]

void distribution_counting( recordtype a[], int n ){
    int i, j, count[m];
    recordtype b[n+1];
    for( j = 0; j < m; j++ ){ count[j] = 0; }
    for( i = 1; i <= n; i++ ){ count[a[i].key]++; }
    for( j = 1; j < m; j++ ){ count[j] += count[j-1]; }
    for( i = n; i >= 1; i-- ){
        b[ count[a[i].key] ] = a[i];
        count[a[i].key]--;
    }
    for( i = 1; i <= n; i++){ a[i] = b[i]; }
}

解説

手順は 3 段階。

1. 度数分布：count[key] に「そのキーが何個あるか」を数える
2. 累積度数分布：count[j] += count[j-1] で「j 以下のキーが全部で何個か」にする
3. 配置：count[key] の値が「ソート後の位置」。置いたらデクリメント

末尾から走査するのは安定性を保つため。同じキー同士の相対順序が、元の配列と同じになる。

計算量は O(n)。比較が無いので理論上は最速クラス。ただしキーの範囲 m が既知で、count 配列が作れることが前提。

---

問15: 基数整列法 radix sort

キーをビット列とみなし、上位ビットから「0 グループ」「1 グループ」に分けて再帰的に整列する（基数交換法）。

/* x を k ビット右へシフトし、その左 j ビットを取り出す */
int bits( int x, int k, int j ){
    return ( x >> k ) & ___①___;
}
 
void radixsort( recordtype a[], int l, int r, int b ){
    int i, j;
    if ( l < r && b >= 0 ){
        i = l; j = r;
        do {
            while ( ___②___ == 0 && i < j ){ i++; }  /* 左から0を探す */
            while ( ___③___ == 1 && i < j ){ j--; }  /* 右から1を探す */
            if ( i != j ){ swap( &a[i], &a[j] ); }
        } while ( j != i );
        if ( bits(a[r].key, b, 1) == 0 ){ j++; }
        radixsort( a, l, j-1, b-1 );   /* 0の部分を再帰 */
        radixsort( a, j, r, b-1 );     /* 1の部分を再帰 */
    }
}

解答

①: ~( ~0 << j )　②: bits( a[i].key, b, 1 )　③: bits( a[j].key, b, 1 )

int bits( int x, int k, int j ){
    return ( x >> k ) & ~( ~0 << j );
}
 
void radixsort( recordtype a[], int l, int r, int b ){
    int i, j;
    if ( l < r && b >= 0 ){
        i = l; j = r;
        do {
            while ( bits( a[i].key, b, 1 ) == 0 && i < j ){ i++; }
            while ( bits( a[j].key, b, 1 ) == 1 && i < j ){ j--; }
            if ( i != j ){ swap( &a[i], &a[j] ); }
        } while ( j != i );
        if ( bits(a[r].key, b, 1) == 0 ){ j++; }
        radixsort( a, l, j-1, b-1 );
        radixsort( a, j, r, b-1 );
    }
}

解説

bits(x, k, j) は「x を k ビット右にずらし、下位 j ビットを取り出す」。~( ~0 << j ) は「下位 j ビットだけ 1」のマスク。

radixsort の do-while はクイックソートの partition とそっくり。b ビット目が 0 の要素を左に、1 の要素を右に分ける。

最上位ビットから始め（32bit なら b=30、符号ビットを除く）、再帰で b-1 に進む。上位から決めるのが「基数交換法」。

下位ビットから distribution counting で整列する方法は「直接基数法（straight radix sort）」と呼ばれ、別に存在する。

問16: マージソート mergesort（配列版）

列を半分に分割 → 各部分を再帰ソート → 併合（マージ）する分割統治法。右半分を逆順にコピーすることで番兵を不要にするのがこの実装の工夫。

void mergesort ( recordtype a[], int l, int r ){
    int i, j, k, m; recordtype b[LIMIT];
    if ( l < r ){
        m = ___①___;                  /* 中央を求める */
        mergesort ( a, l, m );         /* 左半分を再帰 */
        mergesort ( a, ___②___m+1, r );  /* 右半分を再帰 */
        for ( i = m; i >= l; i-- ){ b[i] = a[i]; }   /* 左半分をそのままコピー */
        i = l;
        for ( j = m+1; j <= r; j++ ){ b[___③___r-j] = a[j]; }  /* 右半分を逆順にコピー */
        j = r;
        for ( k = l; k <= r; k++ ){                    /* 両端からマージ */
            if ( ___④___ ){ a[k] = b[i++]; }          /* 左が小さければ左から */
            else { a[k] = b[j--]; }                    /* 右が小さければ右から */
        }
    }
}

解答

①: ( r + l ) / 2　②: m + 1　③: r - ( j - (m+1) )　④: b[i].key < b[j].key

void mergesort ( recordtype a[], int l, int r ){
    int i, j, k, m; recordtype b[LIMIT];
    if ( l < r ){
        m = ( r + l ) / 2;
        mergesort ( a, l, m );
        mergesort ( a, m+1, r );
        for ( i = m; i >= l; i-- ){ b[i] = a[i]; }
        i = l;
        for ( j = m+1; j <= r; j++ ){ b[ r - ( j - (m+1) ) ] = a[j]; }
        j = r;
        for ( k = l; k <= r; k++ ){
            if ( b[i].key < b[j].key ){ a[k] = b[i++]; }
            else { a[k] = b[j--]; }
        }
    }
}

解説

分割は「真ん中で切って、それぞれを再帰」だけ。本体はマージ。

左半分は b の左半分にそのまま、右半分は b の右半分に逆順でコピーする。すると b の左端 i と右端 j から小さい方を取り出していくだけで、どちらが先に尽きても正しく併合できる。

これが「番兵を使わないマージ」のからくり。番兵（a[M+1] = INT_MAX）を置く方式と比べると、この実装では番兵を置く必要がない。

計算量は常に O(n log n)。安定ソート。ただし作業用配列 b が必要。

---

Part 3: 探索（第14回）

問17: 線形探索（番兵あり）

先頭から順に探す線形探索。末尾に番兵 x を置いて、ループ内の比較を 1 つに減らす。

int search( elementtype x, elementtype a[], int N ){
    int i;
    a[N] = x;                     /* 番兵：末尾に x をセット */
    for ( i = 0; ___①___; i++ ) ;  /* 必ず見つかる（番兵で停止） */
    return ___②___;              /* 番兵で止まったら見つからなかった */
}

解答

①: a[i] != x　②: i < N

int search( elementtype x, elementtype a[], int N ){
    int i;
    a[N] = x;
    for ( i = 0; a[i] != x; i++ ) ;
    return i < N;
}

解説

番兵なしの素朴な実装は while ( i < N && a[i] != x ) で、ループごとに3つの演算（i<N, a[i]!=x, i++）がある。

末尾に x を置くと「必ず見つかる」ので、i < N のチェックを外して条件 1 つにできる。見つかった場所が N なら番兵に当たった＝見つからなかった、N 未満なら本当に見つかった。

比較回数は最悪 N 回、成功時平均 N/2 回。

問18: 二分探索 binary search

整列済みの配列が前提。中央と比較して、探索範囲を半分ずつに絞る。

int search( elementtype x, elementtype a[], int N ){
    int l, r, m;
    l = 0; r = N-1;
    while ( l < r ){
        m = ___①___;              /* 中央を求める */
        if ( x < a[m] ){
            r = ___②___;          /* 前半側を探索 */
        } else if ( x > a[m] ){
            l = ___③___;          /* 後半側を探索 */
        } else {
            l = r = m;             /* 見つかった → 範囲を収束 */
        }
    }
    return ( l == r && a[l] == x );
}

解答

①: ( l + r ) / 2　②: m - 1　③: m + 1

int search( elementtype x, elementtype a[], int N ){
    int l, r, m;
    l = 0; r = N-1;
    while ( l < r ){
        m = ( l + r ) / 2;
        if ( x < a[m] ){
            r = m - 1;
        } else if ( x > a[m] ){
            l = m + 1;
        } else {
            l = r = m;
        }
    }
    return ( l == r && a[l] == x );
}

解説

中央 m と x を比較し、x が小さければ左半分（r = m-1）、大きければ右半分（l = m+1）に絞る。

一致したら l = r = m で範囲を 1 点に収束させ、ループを抜ける。最後に「候補が 1 つに絞られて、かつ一致」か確認。

範囲が半分ずつ減るので、比較回数は O(log N)。配列の真ん中にランダムアクセスできるからこそ成り立つ探索。

問19: 内挿探索 interpolation search（挑戦）

二分探索の「中央」を、値の分布から推定した位置に変える。データが一様分布していると効率が良い。

int search( elementtype x, elementtype a[], int N ){
    int l, r, m;
    l = 0; r = N-1;
    while ( l < r ){
        m = ___①___;   /* 内挿：値の比から位置を推定 */
        if ( x < a[m] ){
            r = m - 1;
        } else if ( x > a[m] ){
            l = m + 1;
        } else {
            l = r = m;
        }
    }
    return ( l == r && a[l] == x );
}

解答

①: l + ( x - a[l] ) * ( r - l ) / ( a[r] - a[l] )

int search( elementtype x, elementtype a[], int N ){
    int l, r, m;
    l = 0; r = N-1;
    while ( l < r ){
        m = l + ( x - a[l] ) * ( r - l ) / ( a[r] - a[l] );
        if ( x < a[m] ){
            r = m - 1;
        } else if ( x > a[m] ){
            l = m + 1;
        } else {
            l = r = m;
        }
    }
    return ( l == r && a[l] == x );
}

解説

二分探索と違うのは m の計算式だけ。あとは完全に同じコード。

「x が a[l] と a[r] の間のどこら辺にあるか」を比で推定する：( M - l ) : ( r - l ) = x - a[l] : ( a[r] - a[l] )。辞書で「か」を引くとき、頭からではなく「か行あたり」を開く感覚。

理論上の計算量は O(log log N) と二分探索より速いが、m の計算コストが高いので N が大きくないと実用上は二分探索に負ける。

---

付録: ソート・探索の計算量まとめ

アルゴリズム	最良	平均	最悪	安定	備考
選択ソート	O(n²)	O(n²)	O(n²)	不安定	移動が少ない
挿入ソート	O(n)	O(n²)	O(n²)	安定	ほぼ整列済みで最強
バブルソート	O(n)	O(n²)	O(n²)	安定	交換回数が初期状態依存
シェルソート	-	O(n^3/2)	O(n^3/2)	不安定	挿入ソートの改良
クイックソート	O(n log n)	O(n log n)	O(n²)	不安定	pivot 次第
ヒープソート	O(n log n)	O(n log n)	O(n log n)	不安定	in-place
分布数え上げ	O(n)	O(n)	O(n)	安定	キーの範囲が必要
基数整列	O(n)	O(n)	O(n)	安定	ビット列で分割
マージソート	O(n log n)	O(n log n)	O(n log n)	安定	作業配列が必要
線形探索	O(1)	O(n)	O(n)	-	整列不要
二分探索	O(1)	O(log n)	O(log n)	-	整列済みが前提
内挿探索	O(1)	O(log log n)	O(n)	-	一様分布を仮定