Java | ソートアルゴリズムを体系的に学ぶ

Javaでソートアルゴリズムを体系的に学ぶ（前半）

ソート（並べ替え）は、アルゴリズムの世界で最も基本的でありながら、 「きちんと体系的に理解しているか」がはっきり差になるテーマです。 配列やリストを昇順・降順に並べるだけの話に見えますが、 その裏には計算量、安定性、メモリ使用量、そしてセキュリティやパフォーマンスに直結する設計の違いがあります。

前半では、まず「ソートとは何か」「なぜソートが重要なのか」を整理し、 そのうえで代表的な基本ソート（バブルソート・選択ソート・挿入ソート）を Javaコードとともにかみ砕いて解説していきます。 後半では、より高速なソート（クイックソート・マージソートなど）や Java標準ライブラリの Arrays.sort / Collections.sort の裏側に踏み込みます。

ソートアルゴリズムを学ぶ意味を言語化する

まず、「なぜソートを学ぶのか」をはっきりさせておきます。

ソートは、検索・集計・重複削除・ランキング・レポート生成など、 ほぼすべての業務ロジックの基盤になります。 例えば、ユーザー一覧を名前順に並べる、 ログを時刻順に並べる、 売上データを金額順に並べる、 こうした処理はすべてソートです。

さらに、ソートアルゴリズムを学ぶことで

計算量（O(n²), O(n log n)）の感覚が身につく アルゴリズムの「設計の違い」が見えるようになる Java標準ライブラリの動き方を理解できる セキュリティ・パフォーマンスの観点で「危険なソート」を見抜ける

といった力がつきます。

「とりあえず Arrays.sort を呼ぶ」だけではなく、 その裏にある考え方を理解しておくことが、 一段上のエンジニアになるためのステップです。

ソートの基本概念：昇順・降順・安定性・比較

ソートアルゴリズムを体系的に学ぶためには、 いくつかの基本概念を押さえておく必要があります。

昇順と降順 昇順は「小さいものから大きいものへ」、 降順は「大きいものから小さいものへ」です。 アルゴリズム自体はほぼ同じで、比較条件だけが逆になります。

比較ベースのソート 多くのソートアルゴリズムは「要素同士を比較して順番を決める」方式です。 Javaでは Comparator を使って「何を基準に並べるか」を指定できます。

安定性（stable sort） 安定なソートとは、「同じ値の要素の元の順番が保たれるソート」です。 例えば、同じ名前のユーザーが複数いるとき、 元の登録順を保ったまま名前順に並べ替える、 これが安定なソートのイメージです。

この「安定性」は、複数条件でソートするときに非常に重要になります。 例えば、まず年齢でソートし、その後に名前でソートする、 といった処理を安定なソートで行うと、 「年齢順の中で名前順」が自然に実現できます。

バブルソート：最も素朴なソートをコードで理解する

バブルソート（Bubble Sort）は、 「隣同士を比べて、順番が逆なら入れ替える」ことを 何度も繰り返すソートです。

イメージとしては、 「大きい値が少しずつ右側に“泡のように”浮かんでいく」感じです。

Javaコードは次のようになります。

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}

このコードの動きを、具体的な例で追ってみましょう。

配列 [5, 3, 4, 1] を昇順に並べたいとします。

最初の外側ループ i = 0 のとき、 内側ループで次の比較と入れ替えが行われます。

5 と 3 を比較 → 5 > 3 なので入れ替え → [3, 5, 4, 1] 5 と 4 を比較 → 5 > 4 なので入れ替え → [3, 4, 5, 1] 5 と 1 を比較 → 5 > 1 なので入れ替え → [3, 4, 1, 5]

この時点で「最大値 5」が一番右に移動しました。 これを何度も繰り返すことで、 最終的に配列全体が昇順に並びます。

バブルソートは、 計算量が O(n²) と遅く、実務で使うことはほぼありません。 しかし、「ソートとは何をしているのか」を理解するための 最初の教材として非常に優れています。

選択ソート：最小値を選んで前に持ってくる

選択ソート（Selection Sort）は、 「まだ並べていない部分から最小値を探し、それを先頭に持ってくる」 という操作を繰り返すソートです。

イメージとしては、 「残りの中から一番小さいものを“選んで”前に置く」感じです。

Javaコードは次のようになります。

public static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        int tmp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = tmp;
    }
}

public static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        int tmp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = tmp;
    }
}

このコードの動きを、 配列 [5, 3, 4, 1] で追ってみます。

i = 0 のとき、 [5, 3, 4, 1] の中で最小値は 1（index 3） 5 と 1 を入れ替えて [1, 3, 4, 5]

i = 1 のとき、 残り [3, 4, 5] の中で最小値は 3 そのままなので入れ替えなし

i = 2 のとき、 残り [4, 5] の中で最小値は 4 そのままなので入れ替えなし

結果として [1, 3, 4, 5] になります。

選択ソートも計算量は O(n²) ですが、 「最小値を探して前に持ってくる」という発想が分かりやすく、 アルゴリズムの設計を学ぶうえで良い教材になります。

挿入ソート：カードゲームのように「正しい位置に挿す」

挿入ソート（Insertion Sort）は、 「左側はすでにソート済み」とみなし、 右側から一枚ずつ要素を取り出して、 左側の正しい位置に挿し込んでいくソートです。

トランプを手札に並べるとき、 一枚ずつ「入れるべき位置」を探して挿していく、 あの動きがまさに挿入ソートです。

Javaコードは次のようになります。

public static void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

public static void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

このコードの動きを、 配列 [5, 3, 4, 1] で追ってみます。

最初は [5] が「ソート済み」とみなされます。

i = 1 のとき、key = 3 左側 [5] の中で 3 の位置を探す 5 > 3 なので、5 を右にずらして [5, 5, 4, 1] 3 を先頭に挿して [3, 5, 4, 1]

i = 2 のとき、key = 4 左側 [3, 5] の中で 4 の位置を探す 5 > 4 なので、5 を右にずらして [3, 5, 5, 1] 3 < 4 なので、ここで止めて 4 を挿して [3, 4, 5, 1]

i = 3 のとき、key = 1 左側 [3, 4, 5] の中で 1 の位置を探す 5 > 1 → 右にずらす 4 > 1 → 右にずらす 3 > 1 → 右にずらす 先頭に 1 を挿して [1, 3, 4, 5]

挿入ソートも O(n²) ですが、 「ほぼソート済みの配列」に対しては非常に速く動くという特徴があります。 そのため、実務でも「小さな配列」や「ほぼ整列済みのデータ」に対して 部分的に使われることがあります。

三つの基本ソートを比較して直感を育てる

前半で扱った三つのソートは、 どれも計算量が O(n²) で、 大きなデータには向きません。

しかし、それぞれに「アルゴリズムの性格」があります。

バブルソート 隣同士を比べて入れ替える 実装は簡単だが、無駄な比較が多い

選択ソート 最小値を探して前に持ってくる 比較回数は多いが、入れ替え回数は少ない

挿入ソート 左側をソート済みとみなし、正しい位置に挿す ほぼソート済みの配列に対しては非常に効率が良い

この「性格の違い」を感じられるようになると、 ソートアルゴリズムを「ただのテクニック」ではなく 「設計の選択肢」として捉えられるようになります。

前半のまとめと後半への橋渡し

前半では、ソートアルゴリズムを体系的に学ぶための土台として

ソートの基本概念（昇順・降順・比較・安定性） バブルソートの仕組みとコード 選択ソートの仕組みとコード 挿入ソートの仕組みとコード 三つの基本ソートの性格の違い

を整理しました。

後半では、さらに一歩進んで

高速なソート（クイックソート・マージソート・ヒープソート） 計算量 O(n log n) の意味と直感 Java標準ライブラリの Arrays.sort / Collections.sort の裏側 安定ソート・不安定ソートの実務的な使い分け セキュリティ・パフォーマンスの観点から見た「危険なソート設計」

を、具体的な Java コードとともに解説していきます。