では、7種類のソートの実行時間を計測して比較するベンチマーク版の Java コードを作ります。
特徴：
- 配列サイズを指定してランダム配列を生成
- 各ソートでコピーした配列をソート
- 実行時間をミリ秒で計測
- 結果を一覧で表示
7種類ソートベンチマーク Java コード
import java.util.Arrays;
import java.util.Random;
public class SortBenchmark {
public static void main(String[] args) {
int size = 10000; // 配列サイズ
int[] original = new int[size];
Random rand = new Random();
for (int i = 0; i < size; i++) {
original[i] = rand.nextInt(size);
}
System.out.println("配列サイズ: " + size);
benchmarkSort("バブルソート", original, SortBenchmark::bubbleSort);
benchmarkSort("選択ソート", original, SortBenchmark::selectionSort);
benchmarkSort("挿入ソート", original, SortBenchmark::insertionSort);
benchmarkSort("マージソート", original, arr -> mergeSort(arr, 0, arr.length - 1));
benchmarkSort("クイックソート", original, arr -> quickSort(arr, 0, arr.length - 1));
benchmarkSort("ヒープソート", original, SortBenchmark::heapSort);
benchmarkSort("シェルソート", original, SortBenchmark::shellSort);
}
private static void benchmarkSort(String name, int[] original, Sorter sorter) {
int[] arr = Arrays.copyOf(original, original.length);
long start = System.nanoTime();
sorter.sort(arr);
long end = System.nanoTime();
System.out.printf("%-12s 実行時間: %.3f ms%n", name, (end - start) / 1_000_000.0);
}
@FunctionalInterface
interface Sorter { void sort(int[] arr); }
// ---------------------------
// バブルソート
// ---------------------------
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;
}
}
// ---------------------------
// マージソート
// ---------------------------
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, j = mid + 1, 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++];
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;
}
// ---------------------------
// ヒープソート
// ---------------------------
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 size, int i) {
int largest = i;
int left = 2 * i + 1, right = 2 * i + 2;
if (left < size && arr[left] > arr[largest]) largest = left;
if (right < size && arr[right] > arr[largest]) largest = right;
if (largest != i) {
int tmp = arr[i]; arr[i] = arr[largest]; arr[largest] = tmp;
heapify(arr, size, largest);
}
}
// ---------------------------
// シェルソート
// ---------------------------
public static void shellSort(int[] arr) {
int n = arr.length;
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j = i;
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}
}
ポイント
benchmarkSortでコピー配列をソートし、System.nanoTime()で実行時間計測- 配列サイズを大きくすれば高速ソートと遅いソートの差が顕著に
FunctionalInterface Sorterでコードを簡潔に- バブル・選択・挿入は大きな配列だと遅いので注意（数千〜数万要素程度でOK）