# 練習問題

## 知識の確認

### 選択ソートとバブルソートの最初の反復

配列 `[4, 2, 5, 1, 3]` が与えられます。以下では、いずれも昇順にソートします。

<!-- numbered-subquestions -->

1. 選択ソートの最初の二回の反復をたどり、各反復後の配列と、その時点で確定した位置を書いてください。
2. バブルソートの最初の一回の反復をたどり、配列の状態、交換回数、確定した位置を書いてください。

??? success "解答例"

    1. 最初の二回の反復は、次のとおりです。

        | 反復 | 配列の状態 | 説明 |
        | --- | --- | --- |
        | 1 | `[1, 2, 5, 4, 3]` | 最小要素 1 と先頭を交換します |
        | 2 | `[1, 2, 5, 4, 3]` | 2 はすでにインデックス 1 にあるため、交換は不要です |

        これで最初の二つの位置が確定し、以降は `[5, 4, 3]` から最小要素を選び続けます。

    2. 隣り合う要素を順に比較します。4 と 2 は交換し、4 と 5 は交換せず、5 と 1、5 と 3 を交換すると、
        `[2, 4, 1, 3, 5]` になります。交換は計 3 回です。最大要素 5 が末尾に移動したので、最後の位置が確定します。

### 等しい要素の順序は変わるか

配列 $[2_a, 2_b, 1]$ の $2_a$ と $2_b$ は値が等しく、添字で元の順序を示しています。

<!-- numbered-subquestions -->

1. 選択ソートの一回目の反復後の配列を書いてください。$2_a$ と $2_b$ の相対的な順序は変わりますか。
2. バブルソートの一回目の反復後の配列を書いてください。$2_a$ と $2_b$ の相対的な順序は変わりますか。
3. 前の二問から、等しい要素の元の順序を保つという点で、二つのソートがどう違うかを説明してください。

??? success "解答例"

    1. 選択ソートの一回目では、最小要素 1 を選び、先頭の $2_a$ と交換するので、
        $[1, 2_b, 2_a]$ となります。$2_a$ が $2_b$ の後ろに移り、相対的な順序が変わります。

    2. バブルソートでは、まず $2_a$ と $2_b$ を比較します。等しいので交換せず、次に $2_b$ と 1 を比較して交換するため、
        一回目の反復後は $[2_a, 1, 2_b]$ です。$2_a$ は引き続き $2_b$ より前にあり、相対的な順序は変わりません。

    3. この例では、選択ソートは等しい要素の元の順序を変えます。一方、バブルソートは、左の要素が右の要素より大きい場合にだけ
        隣り合う要素を交換します。等しい要素同士は交換しないため、元の順序を保てます。

### カウントソートと基数ソートの比較

学校で、桁数が 8 桁に固定された多数の学籍番号をソートします。次の問いに答えてください。

<!-- numbered-subquestions -->

1. 最下位桁から始める基数ソートでは、何回の反復が必要ですか。
2. 学籍番号をそのまま整数としてカウントソートすると、使われないカウント位置を大量に用意することになるのはなぜですか。
3. 前の二問から、多数の 8 桁の学籍番号を処理するためにカウントソートと基数ソートのどちらかを選ぶなら、どちらにしますか。理由も説明してください。

??? success "解答例"

    1. 学籍番号は 8 桁なので、最下位桁から最上位桁まで計 8 回処理します。各回は 0～9 による分類だけを行います。

    2. 直接カウントするには、8 桁で取り得るすべての値に位置を用意する必要があります。しかし、実際の生徒が使うのはそのごく一部で、
        ほとんどのカウント位置は 0 のままです。

    3. 基数ソートを選びます。「桁数が固定され、各桁に 10 種類の値しかない」という特徴を利用し、安定な分類を 8 回繰り返すだけで済みます。
        カウントソートで 8 桁の番号全体を整数のインデックスとして使うと、実際には現れない多数の値にカウント位置を用意しなければなりません。

## プログラミング演習

### マージソートで配列を並べる

整数配列 `nums` が与えられます。マージソートを自分で実装し、要素を非減少順に並べて返してください。言語に組み込まれたソート関数は呼び出さないでください。

??? tip "解くためのヒント"

    1. 区間の長さが 1 以下なら、すでに整列済みです
    2. 中点で区間を二つに分け、それぞれを再帰的にソートします
    3. 二つのポインタで整列済みの半区間をマージし、結果を元の配列に書き戻します

[LeetCode](https://leetcode.com/problems/sort-an-array/){ .rounded-button .exercise-button target="_blank" rel="noopener noreferrer" }

### カウントソートで整数配列を並べる

整数配列 `nums` と非負整数 $K$ が与えられます。配列の各要素は $0$ 以上 $K$ 以下です。

カウントソートを実装し、結果を非減少順に `nums` へ書き戻して、`nums` を返してください。
要素間の大小比較で順序を決めたり、言語に組み込まれたソート関数を呼び出したりしてはいけません。

??? tip "解くためのヒント"

    1. 各要素は 0 以上 K 以下なので、値をそのままカウント配列のインデックスに使えます
    2. 一回目の走査では nums を調べ、対応する位置の個数を 1 増やします
    3. 次にカウント配列を 0 から K まで走査します。値 x が出現した回数だけ、nums に x を連続して書き込みます