ソートアルゴリズムのカテゴリ概要

データ配列の順序づけを行う内部ソートは、比較手法とデータ配置の仕組みに基づき「挿入」「交換」「選択」「帰併（マージ）」「分配」の五つのクラスに大別されます。以下に各代表的なアルゴリズムの理論的性質と、構造化・変数名を変更した実装コードを示します。

1. 挿入系ソート

直接挿入ソート（Straight Insertion Sort）

配列を「整列済みPrefix」と「未処理Suffix」に分け、Suffixの要素をPrefix内の正しい位置へ順番に挿入していきます。入力データが部分的にソート済みの場合、比較回数と移動回数が劇的に減少するため、小数値データの並べ替えや実装上のサブルーチンとして頻繁に活用されます。

void insertSort(int[] data) {
    int size = data.length;
    for (int k = 1; k < size; k++) {
        int target = data[k];
        int scan = k - 1;
        // 挿入可能な位置まで左側へ走査
        while (scan >= 0 && data[scan] > target) {
            data[scan + 1] = data[scan];
            scan--;
        }
        data[scan + 1] = target;
    }
}

シェルスソート（Shell Sort）

直接挿入ソートの欠点を補う改良版です。比較間隔（ステップ幅）を当初大きく設定し、要素同士を遠くから入れ替えることで大まかな秩序を整えた後、ステップ幅を漸減させます。最終的にはギャップが1となり直接挿入ソートと同様の処理になりますが、この時点でデータはほぼ整列済みであるため高速化が実現します。

void shellSort(int[] values) {
    int n = values.length;
    // ハッケンベリなどの数列ではなく簡易な2除算による縮小
    for (int step = n / 2; step > 0; step /= 2) {
        for (int i = step; i < n; i++) {
            int temp = values[i];
            int j = i;
            // グループ単位で前方向へシフト
            while (j >= step && values[j - step] > temp) {
                values[j] = values[j - step];
                j -= step;
            }
            values[j] = temp;
        }
    }
}

2. 交換系ソート

バブルソート（Bubble Sort）

隣接する二要素を比較し、大小関係が反転している場合は入れ替える操作を配列端まで繰り返します。内側ループが終了するごとに未ソート領域の最大値が右端に確定します。最適化として、一パスで交換が一切発生しなかった場合は早期終了する判定フラグを組み込むのが標準的な実装パターンです。

void bubbleSort(int[] nums, int count) {
    boolean swapped = true;
    for (int pass = 0; pass < count - 1 && swapped; pass++) {
        swapped = false;
        for (int idx = 0; idx < count - 1 - pass; idx++) {
            if (nums[idx] > nums[idx + 1]) {
                int hold = nums[idx];
                nums[idx] = nums[idx + 1];
                nums[idx + 1] = hold;
                swapped = true;
            }
        }
    }
}

クイックソート（Dual-Pointer Partitioning）

配列から基準値（ピボット）を選択し、それより小さい値を左側、大きい値を右側に配置する「パーティショニング」を再帰的に実行します。双方向インデックスを用いる場合、右端からピボット未満の要素を検索し、左端からピボット以上の要素を検索してから交換処理を実行します。平均計算量が極めて優れており、組み込みライブラリの既定ソートでも広く採用されています。

void quickSort(int[] arr, int low, int high) {
    if (low >= high) return;
    
    int pivot = arr[low];
    int left = low;
    int right = high;
    
    while (left < right) {
        while (left < right && arr[right] >= pivot) right--;
        while (left < right && arr[left] <= pivot) left++;
        
        if (left < right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
    }
    // ピボットを中央に配置
    arr[low] = arr[left];
    arr[left] = pivot;
    
    quickSort(arr, low, left - 1);
    quickSort(arr, left + 1, high);
}

3. 選択系ソート

直接選択ソート（Selection Sort）

未ソート範囲から最小値（あるいは最大値）を探索し、その要素を未ソート範囲の先頭（あるいは末尾）と一度だけ交換する方法です。比較回数は固定ですが、要素の物理的な移動回数が最小限に抑えられる特性を持ちます。

void selectSort(int[] seq, int length) {
    for (int phase = 0; phase < length - 1; phase++) {
        int minIndex = phase;
        for (int cursor = phase + 1; cursor < length; cursor++) {
            if (seq[cursor] < seq[minIndex]) {
                minIndex = cursor;
            }
        }
        if (minIndex != phase) {
            int tmp = seq[phase];
            seq[phase] = seq[minIndex];
            seq[minIndex] = tmp;
        }
    }
}

ヒープソート（Heap Sort）

完全二叉木の状態を配列上で表現するヒープ構造を利用します。まず最大ヒープ（親が子よりも常に大きい状態）を構築し、ルート要素（最大値）を配列末尾と入れ替えます。その後、ヒープサイズを1減らしてトップノードから下方向への条件再調整（sift-down）を繰り返し、これにより降順の取り出しを経て結果として昇順配列が完成します。

public static void heapSort(int[] payload) {
    int total = payload.length;
    
    // 非葉ノード逆順でヒープ初期化
    for (int node = (total - 1) / 2; node >= 0; node--) {
        siftDown(payload, total, node);
    }
    
    // ルートと末尾の交換＋ヒープ縮小＋再調整
    for (int end = total - 1; end > 0; end--) {
        int swapVal = payload[end];
        payload[end] = payload[0];
        payload[0] = swapVal;
        
        siftDown(payload, end, 0);
    }
}

private static void siftDown(int[] tree, int limit, int root) {
    int candidate = tree[root];
    int child = 2 * root + 1;
    
    while (child < limit) {
        int sibling = child + 1;
        if (sibling < limit && tree[child] < tree[sibling]) {
            child++;
        }
        if (candidate >= tree[child]) break;
        
        tree[root] = tree[child];
        root = child;
        child = 2 * child + 1;
    }
    tree[root] = candidate;
}

4. 帰併ソート（Merge Sort）

配列を再帰的に二つに分割し、それぞれを個別に整列させた後に、両者を一つの整列済み配列へと融合（マージ）する手法です。分割・統治法（Divide and Conquer）の典型例であり、比較ベースのソートアルゴリズムの中で最悪計算量も一定値に収まります。

5. 分配ソート（Distribution Sort）

要素間の直接比較を行わず、データ自体が持つ桁情報や値の範囲に基づいて箱（バケット）に分類・連結することで整列させる非比較ソートです。

• バケットソート：対象範囲を等幅の区間に分割し、各バケット内に格納します。データが均等分布している場合に線形時間O(n)に近い処理速度を発揮します。
• ラディックスソート：十進数やバイナリデータを1桁ずつキーとして扱い、下位桁から上位桁へ向かって安定ソートを逐次適用します。例えば整数群に対し1の位でバケット振り分け→結合、次いで10の位で同様の処理を施すことで、最終的に全桁が整列された状態になります。外部記憶装置へのアクセス最適化や固定長キーのソートに威力を発揮します。

総合特性比較

時間計算量

• O(n²)：直接挿入ソート、直接選択ソート、バブルソート
• O(n log₂n)：クイックソート、マージソート、ヒープソート
• シェルスソート：ギャップ数列に依拠。実用的にはO(n¹·²⁵)〜O(n log₂n)
• ラディックスソート：O(d × (r_d + n)) ｜ d: キー位数、r_d: 基数、n: 要素数

安定性（同等値の相対順序維持）

• 安定：直接挿入ソート、バブルソート、マージソート、ラディックスソート、バケットソート
• 不安定：直接選択ソート、シェルソート、クイックソート、ヒープソート

追加メモリ使用量（Auxiliary Space）

• O(1)：直接挿入、直接選択、バブル、シェル、ヒープ（すべて原地ソート可能）
• O(log₂n)：クイックソート（再帰コールスタックの深さに比例）
• O(n)：マージソート（融合用の一時配列必須）
• O(n + r_d)：ラディックスソート（計数配列またはバケットリストの確保が必要）