問題概要

非負とは限らない整数からなる配列 nums が与えられる。この配列を昇順に並べ替える関数を実装する。制約条件として、配列長は最大で 50,000、各要素の値は -50,000 から 50,000 の範囲内である。

基本的なソート手法

バブルソート（改良なし）

隣接する要素を比較し、必要に応じて交換を行うことで、毎回最大値が末尾に移動する。このプロセスを繰り返す。

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

最適化されたバブルソート

一巡の中で交換が一度も発生しなければ、既に整列済みと判断して早期終了できる。

public void optimizedBubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

選択ソート

未整列部分から最小値を探し、それを未整列部分の先頭と交換する。これを繰り返す。

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

挿入ソート

整列済み領域を拡大しながら、新しい要素を適切な位置に挿入する。

public void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; 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;
    }
}

二分挿入ソート

挿入位置を線形探索ではなく、二分探索で求める。シフト操作は依然O(n)だが、比較回数を削減できる。

public void binaryInsertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int left = 0, right = i - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] > key) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        arr[left] = key;
    }
}

効率的なソートアルゴリズム

マージソート

分割統治法に基づく安定ソート。配列を半分に分割し、それぞれを再帰的にソートした後、結果をマージする。

public void mergeSort(int[] arr, int l, int r, int[] buf) {
    if (l >= r) return;
    
    // 小サイズでは挿入ソートに切り替え
    if (r - l + 1 <= 16) {
        insertionSubSort(arr, l, r);
        return;
    }
    
    int m = l + (r - l) / 2;
    mergeSort(arr, l, m, buf);
    mergeSort(arr, m + 1, r, buf);
    
    if (arr[m] <= arr[m + 1]) return; // 既に整列済み
    
    System.arraycopy(arr, l, buf, l, r - l + 1);
    int i = l, j = m + 1;
    for (int k = l; k <= r; k++) {
        if (i > m) {
            arr[k] = buf[j++];
        } else if (j > r) {
            arr[k] = buf[i++];
        } else if (buf[i] <= buf[j]) {
            arr[k] = buf[i++];
        } else {
            arr[k] = buf[j++];
        }
    }
}

private void insertionSubSort(int[] arr, int l, int r) {
    for (int i = l + 1; i <= r; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= l && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

クイックソート（ピボット最適化付き）

ランダムなピボットを選択し、配列を分割する。小規模な部分配列では挿入ソートを使用してパフォーマンスを向上させる。

private static final int THRESHOLD = 16;
private Random rand = new Random();

public void quickSort(int[] arr, int low, int high) {
    if (low >= high) return;

    if (high - low + 1 <= THRESHOLD) {
        insertionSubSort(arr, low, high);
        return;
    }

    int pivotIndex = partition(arr, low, high);
    quickSort(arr, low, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, high);
}

private int partition(int[] arr, int l, int r) {
    int randomPivot = l + rand.nextInt(r - l + 1);
    swap(arr, l, randomPivot);

    int pivotVal = arr[l];
    int i = l + 1, j = r;

    while (true) {
        while (i <= r && arr[i] < pivotVal) i++;
        while (j > l && arr[j] > pivotVal) j--;
        if (i >= j) break;
        swap(arr, i++, j--);
    }
    swap(arr, l, j);
    return j;
}

private void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

解法の選定と性能比較

• O(n²) 手法（バブル・選択・挿入）：教育目的や極小データ向け
• O(n log n) 手法：実用的。マージソートは安定かつ予測可能な性能、クイックソートは平均高速だが最悪ケースに注意
• ハイブリッド戦略：クイックソート＋挿入ソートは現実的な最適化