ここでは Java でのバブルソート・選択ソート・高速（クイック）ソート の基本的な実装例を示します。
どれも配列を昇順にソートするサンプルです。
import java.util.Arrays;
public class SortExample {
public static void main(String[] args) {
int[] array = {7, 2, 9, 4, 3, 8, 1, 6};
System.out.println("元の配列: " + Arrays.toString(array));
// バブルソート
int[] bubbleArray = Arrays.copyOf(array, array.length);
bubbleSort(bubbleArray);
System.out.println("バブルソート: " + Arrays.toString(bubbleArray));
// 選択ソート
int[] selectionArray = Arrays.copyOf(array, array.length);
selectionSort(selectionArray);
System.out.println("選択ソート: " + Arrays.toString(selectionArray));
// 高速ソート（クイックソート）
int[] quickArray = Arrays.copyOf(array, array.length);
quickSort(quickArray, 0, quickArray.length - 1);
System.out.println("高速ソート(クイックソート): " + Arrays.toString(quickArray));
}
// --------------------------
// バブルソート
// --------------------------
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 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;
}
}
ポイント
- バブルソート
- 隣り合う要素を比較して大きい方を右に移動
- シンプルだが遅い（O(n²)）
- 選択ソート
- 未ソート部分の最小値を選んで先頭と交換
- 計算量はバブルと同じく O(n²)
- 高速ソート（クイックソート）
- ピボットを決めて配列を2分割、再帰的にソート
- 平均 O(n log n) で高速