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

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

前半では、バブルソート・選択ソート・挿入ソートという「基本ソート」を通して、 ソートの仕組みと性格の違いを整理しました。 後半では、実務で主役になる 高速ソート（クイックソート・マージソート・ヒープソート）、 そして Java標準ライブラリのソートの裏側、 さらに 計算量・安定性・セキュリティの観点から見たソート設計 を深掘りしていきます。

ソートは「ただ並べ替えるだけ」の処理ではなく、 パフォーマンスと安全性に直結する重要なアルゴリズムです。 ここからが、ソートを“使いこなす”ための本番です。

クイックソート：速いけれど「偏り」に弱いソート

クイックソート（Quick Sort）は、 平均的には非常に速く、実務でもよく使われるソートです。 計算量は平均で O(n log n)、 「分割して征服する（Divide and Conquer）」の代表的なアルゴリズムです。

クイックソートの基本的な考え方は次の通りです。

ある要素を「軸（ピボット）」として選ぶ 配列を「ピボットより小さいグループ」と「ピボットより大きいグループ」に分ける それぞれのグループに対して再帰的に同じ処理を行う

Javaでのシンプルな実装例を見てみます。

public static void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;

    int pivot = arr[(left + right) / 2];
    int i = left;
    int j = right;

    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
            j--;
        }
    }

    quickSort(arr, left, j);
    quickSort(arr, i, right);
}

public static void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;

    int pivot = arr[(left + right) / 2];
    int i = left;
    int j = right;

    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
            j--;
        }
    }

    quickSort(arr, left, j);
    quickSort(arr, i, right);
}

このコードは、 「真ん中の要素をピボットにして、左右に分ける」 という典型的なクイックソートの形です。

クイックソートの重要なポイントは、 「平均的には速いが、最悪の場合 O(n²) になる」という点です。 例えば、すでに昇順に並んだ配列に対して、 常に先頭をピボットに選ぶような実装をすると、 分割が極端に偏り、性能が悪化します。

セキュリティの観点では、 攻撃者が「わざと最悪ケースになるような入力」を送ることで、 クイックソートの性能を落とす可能性があります。 そのため、実務では「ピボットの選び方」を工夫したり、 最悪ケースを避けるための対策が取られます。

マージソート：安定で、常に O(n log n) のソート

マージソート（Merge Sort）は、 「分割してから、マージ（結合）する」ソートです。 クイックソートと同じく分割統治法ですが、 計算量は常に O(n log n) で、 安定ソートであるという大きな特徴があります。

マージソートの基本的な流れは次の通りです。

配列を半分に分割する それぞれを再帰的にソートする 最後に二つのソート済み配列を「マージ」する

Javaでの実装例を見てみます。

public static void mergeSort(int[] arr) {
    if (arr.length <= 1) return;
    mergeSortRecursive(arr, 0, arr.length - 1);
}

private static void mergeSortRecursive(int[] arr, int left, int right) {
    if (left >= right) return;

    int mid = (left + right) / 2;
    mergeSortRecursive(arr, left, mid);
    mergeSortRecursive(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

private static void merge(int[] arr, int left, int mid, int right) {
    int[] tmp = new int[right - left + 1];
    int i = left;
    int j = mid + 1;
    int k = 0;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            tmp[k++] = arr[i++];
        } else {
            tmp[k++] = arr[j++];
        }
    }

    while (i <= mid) {
        tmp[k++] = arr[i++];
    }
    while (j <= right) {
        tmp[k++] = arr[j++];
    }

    System.arraycopy(tmp, 0, arr, left, tmp.length);
}

public static void mergeSort(int[] arr) {
    if (arr.length <= 1) return;
    mergeSortRecursive(arr, 0, arr.length - 1);
}

private static void mergeSortRecursive(int[] arr, int left, int right) {
    if (left >= right) return;

    int mid = (left + right) / 2;
    mergeSortRecursive(arr, left, mid);
    mergeSortRecursive(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

private static void merge(int[] arr, int left, int mid, int right) {
    int[] tmp = new int[right - left + 1];
    int i = left;
    int j = mid + 1;
    int k = 0;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            tmp[k++] = arr[i++];
        } else {
            tmp[k++] = arr[j++];
        }
    }

    while (i <= mid) {
        tmp[k++] = arr[i++];
    }
    while (j <= right) {
        tmp[k++] = arr[j++];
    }

    System.arraycopy(tmp, 0, arr, left, tmp.length);
}

マージソートの重要な特徴は次の二つです。

計算量が常に O(n log n) で、最悪ケースでも性能が安定している 安定ソートであり、同じ値の要素の元の順番が保たれる

この「安定性」は、 複数条件でソートするときに非常に重要です。 例えば、ユーザー一覧を「年齢順＋名前順」で並べたいとき、 安定ソートを使うことで自然な並びを実現できます。

ヒープソート：ヒープ構造を使った O(n log n) ソート

ヒープソート（Heap Sort）は、 「ヒープ」というデータ構造を使ってソートを行うアルゴリズムです。 ヒープは「親が子より常に大きい（または小さい）」という性質を持つ木構造で、 最大値（または最小値）を効率よく取り出すことができます。

ヒープソートの基本的な流れは次の通りです。

配列をヒープ構造に変換する（ヒープ化） 最大値（または最小値）を取り出して、末尾に配置する ヒープを再調整する これを繰り返す

Javaでのシンプルな実装例を見てみます。

public static void heapSort(int[] arr) {
    int n = arr.length;

    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    for (int i = n - 1; i > 0; i--) {
        int tmp = arr[0];
        arr[0] = arr[i];
        arr[i] = tmp;

        heapify(arr, i, 0);
    }
}

private static void heapify(int[] arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    if (largest != i) {
        int tmp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = tmp;
        heapify(arr, n, largest);
    }
}

public static void heapSort(int[] arr) {
    int n = arr.length;

    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    for (int i = n - 1; i > 0; i--) {
        int tmp = arr[0];
        arr[0] = arr[i];
        arr[i] = tmp;

        heapify(arr, i, 0);
    }
}

private static void heapify(int[] arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    if (largest != i) {
        int tmp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = tmp;
        heapify(arr, n, largest);
    }
}

ヒープソートの特徴は次の通りです。

計算量は常に O(n log n) 追加の配列をほとんど使わず、メモリ効率が良い 安定ソートではない（同じ値の順番は保証されない）

メモリ使用量を抑えたい場面では、 ヒープソートのような「インプレースな O(n log n) ソート」が選択肢になります。

Java標準ライブラリのソートの裏側

実務では、ほとんどの場面で 自前でソートアルゴリズムを書くことはありません。 代わりに、Java標準ライブラリの Arrays.sort や Collections.sort を使います。

ここで重要なのは、「標準ライブラリがどんなソートを使っているか」を ざっくり理解しておくことです。

Arrays.sort(int[]) プリミティブ型の配列に対しては、 高速なクイックソートベースのアルゴリズムが使われます。 Javaのバージョンによって実装は変わりますが、 基本的には O(n log n) の高速ソートです。

Arrays.sort(Object[]) や Collections.sort(List<T>) オブジェクトに対しては、 安定なマージソートベースのアルゴリズムが使われます。 これにより、「同じキーを持つ要素の順番」が保たれます。

この「プリミティブは不安定ソート、オブジェクトは安定ソート」という違いは、 実務で意外と重要です。 例えば、ログエントリやユーザー情報など、 「同じキーを持つ要素の順番」が意味を持つデータでは、 安定ソートであることが前提になります。

安定ソートと不安定ソートの実務的な使い分け

安定ソートとは、「同じ値の要素の元の順番が保たれるソート」です。 不安定ソートでは、同じ値の要素の順番が入れ替わる可能性があります。

実務では、次のような場面で安定ソートが重要になります。

ユーザー一覧を「年齢順＋名前順」で並べたい ログを「時刻順＋ユーザーID順」で並べたい 売上データを「日付順＋商品ID順」で並べたい

このような「複数条件ソート」を行うとき、 安定ソートを使うことで自然な並びを実現できます。

一方で、不安定ソートでも問題ない場面も多くあります。 例えば、単純に数値を昇順に並べたいだけなら、 安定性はほとんど意味を持ちません。

ソートアルゴリズムを選ぶときは、 「安定性が必要かどうか」を意識することが重要です。

セキュリティ・パフォーマンスの観点から見た「危険なソート設計」

ソートは一見すると「安全な処理」に見えますが、 セキュリティスペシャリストの視点では、 次のような危険性を持っています。

入力サイズが極端に大きい場合 ソートは O(n log n) でも、n が巨大だと処理時間が急増します。 攻撃者が「異常に大きなリスト」を送ることで、 サーバーに負荷をかける可能性があります。

最悪ケースに弱いアルゴリズムを使っている場合 クイックソートのように、 最悪ケースで O(n²) になるアルゴリズムを 外部入力に対して使うと、 攻撃者が「最悪ケースを誘発する入力」を送ることで 性能を意図的に落とす可能性があります。

比較関数（Comparator）が遅い場合 ソートは「比較回数」が多いため、 比較関数が重いと全体の性能に直結します。 外部サービス呼び出しやDBアクセスを含む比較関数は非常に危険です。

安全なソート設計としては、次のような方針が重要です。

入力サイズに上限を設ける 最悪ケースに強いアルゴリズム（マージソートなど）を選ぶ 比較関数を軽く保つ（純粋な計算だけにする） ソート前に「異常なデータ」をフィルタリングする

ソートは「ただ並べ替えるだけ」ではなく、 サービス全体のパフォーマンスと安全性に直結する処理です。

後半のまとめ

後半では、ソートアルゴリズムを体系的に学ぶうえで重要な

クイックソートの仕組みと平均 O(n log n)／最悪 O(n²) マージソートの安定性と常に O(n log n) という強さ ヒープソートのメモリ効率とインプレースな O(n log n) Java標準ライブラリの Arrays.sort / Collections.sort の裏側 安定ソート・不安定ソートの実務的な使い分け セキュリティ・パフォーマンスの観点から見た危険なソート設計

を整理しました。

ソートアルゴリズムを体系的に理解すると、 「どの場面でどのソートを選ぶべきか」を 自分の頭で判断できるようになります。 それは、単にコードを書く力ではなく、 システム全体を設計する力につながっていきます。