前回の バブル・選択・クイック に加えて、今回は 挿入ソート・マージソート を含めた 5 つのソートを同時比較できる完全コード を作成します。
以下はそのままコンパイル＆実行できます。
挿入ソート & マージソートを追加した完全比較コード（Java）
import java.util.Arrays;
public class SortComparisonAll {
public static void main(String[] args) {
int[] original = {5, 3, 8, 1, 4};
System.out.println("元の配列: " + Arrays.toString(original));
// バブルソート
int[] bubbleArr = Arrays.copyOf(original, original.length);
bubbleSort(bubbleArr);
System.out.println("バブルソート: " + Arrays.toString(bubbleArr));
// 選択ソート
int[] selectArr = Arrays.copyOf(original, original.length);
selectionSort(selectArr);
System.out.println("選択ソート: " + Arrays.toString(selectArr));
// 挿入ソート
int[] insertArr = Arrays.copyOf(original, original.length);
insertionSort(insertArr);
System.out.println("挿入ソート: " + Arrays.toString(insertArr));
// マージソート
int[] mergeArr = Arrays.copyOf(original, original.length);
mergeSort(mergeArr, 0, mergeArr.length - 1);
System.out.println("マージソート: " + Arrays.toString(mergeArr));
// クイックソート
int[] quickArr = Arrays.copyOf(original, original.length);
quickSort(quickArr, 0, quickArr.length - 1);
System.out.println("クイックソート: " + Arrays.toString(quickArr));
}
// ======================================================
// バブルソート
// ======================================================
public static void bubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
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;
swapped = true;
}
}
if (!swapped) break;
}
}
// ======================================================
// 選択ソート
// ======================================================
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 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;
}
}
// ======================================================
// マージソート（Divide & Conquer）
// ======================================================
public static void mergeSort(int[] arr, int left, int right) {
if (left >= right) return;
int mid = (left + right) / 2;
mergeSort(arr, left, mid); // 左半分
mergeSort(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;
// 小さい方を順に tmp へ
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++];
// tmp を元の配列へコピー
for (int t = 0; t < tmp.length; t++) {
arr[left + t] = tmp[t];
}
}
// ======================================================
// クイックソート
// ======================================================
public static void quickSort(int[] arr, int left, int right) {
if (left >= right) return;
int pivot = arr[(left + right) / 2];
int index = partition(arr, left, right, pivot);
quickSort(arr, left, index - 1);
quickSort(arr, index, right);
}
private static int partition(int[] arr, int left, int right, int pivot) {
while (left <= right) {
while (arr[left] < pivot) left++;
while (arr[right] > pivot) right--;
if (left <= right) {
int tmp = arr[left]; arr[left] = arr[right]; arr[right] = tmp;
left++; right--;
}
}
return left;
}
}
実行例
元の配列: [5, 3, 8, 1, 4]
バブルソート: [1, 3, 4, 5, 8]
選択ソート: [1, 3, 4, 5, 8]
挿入ソート: [1, 3, 4, 5, 8]
マージソート: [1, 3, 4, 5, 8]
クイックソート: [1, 3, 4, 5, 8]
それぞれの特徴（超シンプル比較）
| ソート | 特徴 | 計算量 |
|---|---|---|
| バブルソート | 隣を交換するだけで超簡単 | O(n²) |
| 選択ソート | 比較多いが交換は少ない | O(n²) |
| 挿入ソート | ほぼ整ったデータに超強い | O(n²) （最良 O(n)） |
| マージソート | 安定で高速。安定ソートの代表 | O(n log n) |
| クイックソート | 平均最速。実務レベル | O(n log n)（最悪 O(n²)） |