演習: 探索とソート

各問題のコードは、Main クラスの中に書く前提です。main メソッドの外に問題で指定されたメソッドを static として定義し、main から呼び出してください。

public class Main {
    public static void main(String[] args) {
        // 入力データを用意してメソッドを呼び出す
    }

    // 問題で指定されたメソッドをここに定義する
    static 戻り値の型 メソッド名(引数の型 引数名, ...) {
        // 処理
        return 値;
    }
}

本章では、データを ArrayList<Integer> や ArrayList<String> で扱います。

リテラルから ArrayList を作るには Arrays.asList と組み合わせる書き方が便利です。演習: ArrayList で add を繰り返した形と同じ結果を、リテラルから一括で作れます。

import java.util.ArrayList;
import java.util.Arrays;

ArrayList<Integer> numbers = new ArrayList<>(Arrays.asList(3, 1, 4, 1, 5));

8-A. 線形探索

ArrayList<Integer> の先頭から順に値を比較し、target と一致する要素のインデックスを返すメソッド linearSearch を作成してください。見つからない場合は -1 を返します。

static int linearSearch(ArrayList<Integer> list, int target) {
    // 実装
}

main での呼び出し例:

ArrayList<Integer> numbers = new ArrayList<>(Arrays.asList(7, 2, 9, 4, 6, 1, 8));
System.out.println("見つかった位置: " + linearSearch(numbers, 4));

出力例:

見つかった位置: 3

target を 5 のような存在しない値に変えて、-1 が返ることも確認してください。

ヒント

戻り値を保持する変数を -1 で初期化しておき、リストを走査する中で一致を見つけたら値を更新して break でループを抜けます。ループ後の変数の値をそのまま返せば、見つからない場合も -1 のままです。

8-B. 二分探索

ソート済みの ArrayList<Integer> で target を探し、見つかったインデックスを返すメソッド binarySearch を作成してください。見つからない場合は -1 を返します。

static int binarySearch(ArrayList<Integer> list, int target) {
    // 実装
}

main での呼び出し例:

ArrayList<Integer> sorted = new ArrayList<>(Arrays.asList(1, 3, 5, 7, 9, 11, 13, 15, 17, 19));
System.out.println("見つかった位置: " + binarySearch(sorted, 13));

出力例:

見つかった位置: 6

ヒント

探索範囲を left と right の2つのインデックスで管理します。中央インデックスの値（list.get(mid)）と target を比較し、target の方が大きければ右半分に、小さければ左半分に範囲を絞ります。これを left > right になるまで繰り返します。

8-C. 計算量の比較（線形 vs 二分）

100万要素のソート済みリストを作り、8-A の linearSearch と 8-B の binarySearch で同じ値を探して、それぞれの実行時間を測定して出力してください。target には末尾の値（最悪ケース）を指定します。

int size = 1_000_000;
ArrayList<Integer> sorted = new ArrayList<>(size);
for (int i = 0; i < size; i++) {
    sorted.add(i);
}
int target = size - 1;

出力例（環境により実際の時間は異なります）:

線形探索: 8 ms
二分探索: 0 ms

線形探索 O(n) と二分探索 O(log n) の計算量の差が、実時間にそのまま表れます。

ヒント

時間測定には System.nanoTime() または System.currentTimeMillis() を使います。探索の前後で時刻を取得し、差分が経過時間です。

• nanoTime(): ナノ秒単位（10^-9 秒）、短時間の測定に向く
• currentTimeMillis(): ミリ秒単位（10^-3 秒）

8-D. 二分探索（最初の出現位置）

ソート済みの ArrayList<Integer> で、重複する値があるとき、target が最初に現れるインデックスを返すメソッド firstBinarySearch を作成してください。見つからない場合は -1 を返します。

static int firstBinarySearch(ArrayList<Integer> list, int target) {
    // 実装
}

main での呼び出し例:

ArrayList<Integer> sorted = new ArrayList<>(Arrays.asList(1, 2, 2, 2, 3, 4, 5));
System.out.println("最初の位置: " + firstBinarySearch(sorted, 2));

出力例:

最初の位置: 1

target を 6 のような存在しない値に変えて、-1 が返ることも確認してください。

ヒント

通常の二分探索だと、見つかった位置が最初とは限りません。中央のインデックスで target が見つかっても、それより左に同じ値があるかもしれないためです。

target を見つけた後、さらに左に同じ値がないか探し続ける形に二分探索を書き換えます。一致したときに範囲を左半分に狭め続けると、最も左の出現位置が求まります。

8-E. バブルソート

バブルソートを実装し、ArrayList<Integer> を昇順に並べ替えるメソッド bubbleSort を作成してください。元のリストを直接書き換えます。

static void bubbleSort(ArrayList<Integer> list) {
    // 実装
}

main での呼び出し例:

ArrayList<Integer> numbers = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9, 3, 7, 4, 6));
bubbleSort(numbers);
System.out.println(numbers);

出力例:

[1, 2, 3, 4, 5, 6, 7, 8, 9]

ヒント

バブルソートは、隣接する2つの要素を比較し、順序が逆なら交換します。1回の走査で最大値が末尾に「浮かび上がる」ように移動します。これを n - 1 回繰り返します。

要素の交換は 7-J. Fisher-Yates シャッフル（ArrayList 版）と同じく get / set と一時変数を使います。

8-F. 選択ソート

選択ソートを実装し、ArrayList<Integer> を昇順に並べ替えるメソッド selectionSort を作成してください。元のリストを直接書き換えます。

static void selectionSort(ArrayList<Integer> list) {
    // 実装
}

main での呼び出し例:

ArrayList<Integer> numbers = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9, 3, 7, 4, 6));
selectionSort(numbers);
System.out.println(numbers);

出力例:

[1, 2, 3, 4, 5, 6, 7, 8, 9]

ヒント

選択ソートは、未ソート部分の中から最小値を見つけて、その値を未ソート部分の先頭と交換します。これを繰り返します。

外側のループで「未ソート部分の先頭」を進め、内側のループで「未ソート部分の最小値のインデックス」を探します。最後に未ソート部分の先頭と最小値の位置を交換します。

8-G. 挿入ソート

挿入ソートを実装し、ArrayList<Integer> を昇順に並べ替えるメソッド insertionSort を作成してください。元のリストを直接書き換えます。

static void insertionSort(ArrayList<Integer> list) {
    // 実装
}

main での呼び出し例:

ArrayList<Integer> numbers = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9, 3, 7, 4, 6));
insertionSort(numbers);
System.out.println(numbers);

出力例:

[1, 2, 3, 4, 5, 6, 7, 8, 9]

ヒント

挿入ソートは、リストの左側を「ソート済み部分」、右側を「未ソート部分」と見立て、未ソート部分の先頭をソート済み部分の正しい位置に挿入します。

i を 1 から始めて、list.get(i) をソート済み部分（インデックス 0 から i - 1）の正しい位置に挿入します。挿入位置を見つけるには、ソート済み部分を右から左に走査し、対象より大きい要素を1つずつ右にずらします。

8-H. 文字列のソート

ArrayList<String> を辞書順に並べ替えるメソッド sortStrings を作成してください。元のリストを直接書き換えます。ソート方法は 8-E から 8-G のいずれかを採用してください。

static void sortStrings(ArrayList<String> list) {
    // 実装
}

main での呼び出し例:

ArrayList<String> names = new ArrayList<>(Arrays.asList("Tanaka", "Suzuki", "Sato", "Yamada", "Ito"));
sortStrings(names);
System.out.println(names);

出力例:

[Ito, Sato, Suzuki, Tanaka, Yamada]

ヒント

String の比較には < や > は使えません。代わりに a.compareTo(b) メソッドを使います。

• a が b より辞書順で前 → 負の値
• a と b が等しい → 0
• a が b より辞書順で後 → 正の値

を返します。8-E から 8-G で書いたソートのうち、< や > での比較部分を compareTo の符号判定に書き換えれば、同じ流れでソートできます。

8-I. k番目に小さい値

ArrayList<Integer> の中で、k 番目に小さい値を返すメソッド kthSmallest を作成してください（k = 1 が最小値）。

static int kthSmallest(ArrayList<Integer> list, int k) {
    // 実装
}

main での呼び出し例:

ArrayList<Integer> numbers = new ArrayList<>(Arrays.asList(15, 8, 23, 4, 12, 7, 19, 2, 11));
System.out.println("3番目に小さい値: " + kthSmallest(numbers, 3));

出力例:

3番目に小さい値: 7

k を 1 や 9 に変えても正しく動くことを確認してください。

ヒント

8-E から 8-G のいずれかでソートしてから、インデックス k - 1 の要素を取り出します。ソートはリストを直接書き換えるので、元のリストを保持したい場合はコピーしてからソートします。

k の範囲チェック（k < 1 || k > list.size()）を入れると堅牢になります。

8-J. ソート済みリストのマージ

2つのソート済みリスト a と b を、1つのソート済みリストに統合して返すメソッド merge を作成してください。マージソートの中核となる古典的な操作です。

static ArrayList<Integer> merge(ArrayList<Integer> a, ArrayList<Integer> b) {
    // 実装
}

main での呼び出し例:

ArrayList<Integer> a = new ArrayList<>(Arrays.asList(1, 3, 5, 7, 9));
ArrayList<Integer> b = new ArrayList<>(Arrays.asList(2, 4, 6, 8, 10));
System.out.println(merge(a, b));

出力例:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

結合してからソートすると O((n + m) log(n + m)) ですが、ソート済みであることを利用すれば O(n + m) で解けます。

ヒント

2 ポインタ法（two pointers）で解きます。a 用と b 用のインデックスを2つ用意し、両リストの先頭から進めていきます。それぞれの先頭を比較して、結果リストに小さい方を追加し、追加した側のインデックスを進めます。どちらかが尽きたら、残りをそのまま結果に追加します。

両リストを1回ずつしか走査しないので O(n + m)。