【Java】アルゴリズムの基本！単純選択法の自作と「Arrays.sort()」の凄さ

 プログラムでデータを並べ替える「ソート」。Javaには便利な標準メソッドがありますが、その内部ロジックを知ることは、プログラミング脳を鍛える最高のトレーニングになります。

今回は、直感的なアルゴリズムである**「単純選択法（選択ソート）」**の解説と、実務で使われる標準メソッドの驚くべき効率性について解説します。

---

1. 単純選択法（選択ソート）の仕組み

単純選択法は、**「未整列の部分から最小値を探し、先頭と交換する」**という作業を繰り返す手法です。

処理の4ステップ

1. データの中から最小値を探す。

2. 最小値と、未整列部分の先頭を入れ替える。

3. 先頭を「整列済み」として、対象を一つ後ろにずらす。

4. 未整列のデータが残り1つになるまで繰り返す。

---

2. 推移図（トレース表）

[5, 3, 8, 1, 2] を昇順（小さい順）に並べ替える様子です。

「|」の左側が整列済み、右側が未整列を表します。

ステップ	配列の状態（ | より右が未整列）	見つけた最小値	入れ替え内容
初期状態	[ 5, 3, 8, 1, 2 ]	-	-
1周目	[ 1, | 3, 8, 5, 2 ]	1	5 と 1 を交換
2周目	[ 1, 2, | 8, 5, 3 ]	2	3 と 2 を交換
3周目	[ 1, 2, 3, | 5, 8 ]	3	8 と 3 を交換
4周目	[ 1, 2, 3, 5, | 8 ]	5	入れ替えなし
完了	[ 1, 2, 3, 5, 8 ]	-	ソート完了

---

3. Javaでの実装例

2重の for 文を使って、最小値の探索と交換を実装します。

Java

public class SelectionSort {
    public static void main(String[] args) {
        int[] data = {5, 3, 8, 1, 2};

        for (int i = 0; i < data.length - 1; i++) {
            int minIndex = i; // 最小値がある位置を保持

            // 未整列部分から最小値を探す
            for (int j = i + 1; j < data.length; j++) {
                if (data[j] < data[minIndex]) {
                    minIndex = j;
                }
            }

            // 最小値と先頭を交換（スワップ）
            int temp = data[i];
            data[i] = data[minIndex];
            data[minIndex] = temp;
        }

        // 結果出力
        for (int val : data) {
            System.out.print(val + " ");
        }
    }
}

---

4. 計算量と「O表記」：なぜ自作は遅いのか？

アルゴリズムの効率を表す指標を 計算量（O：オーダー記法） と呼びます。

単純選択法の計算量：O(n^2)

このアルゴリズムは、データ量 nに対して2重のループ処理を行うため、計算量は O(n^2) となります。

• データが 10倍 になると、手間は 100倍 に増えます。

• 数万件のデータを扱うには非常に時間がかかり、実務には不向きです。

---

5. 最強の標準メソッド：Arrays.sort()

実務でソートを行う場合は、Java標準の Arrays.sort() を使います。

Java

import java.util.Arrays;
Arrays.sort(data);

内部アルゴリズムと計算量

Arrays.sort() は、データ型に応じて Dual-Pivot Quicksort や TimSort といった高度なアルゴリズムを採用しています。

• 計算量：O(n log n)

• 効率の差：データが1万件ある場合、単純選択法が1億回の計算を必要とするのに対し、Arrays.sort() はわずか13万回程度で終了します。

---

6. まとめ

• 単純選択法は、最小値を探して詰める基本のアルゴリズム。仕組みの理解に最適。

• 計算量 O(n^2) はデータ量に弱いため、実戦向きではない。

• 実務では O(n \log n) で動く Arrays.sort() を使うのが鉄則。

「中身を知った上で、最適な道具（メソッド）を選ぶ」。これが良いエンジニアへの第一歩です。