バブルソート

隣接要素を比較して交換するアルゴリズム。最大値を末尾に移動させる処理を繰り返す。

public class BubbleSort {
    public static void executeSort(int[] array) {
        int length = array.length;
        for (int i = 0; i < length - 1; i++) {
            for (int j = 0; j < length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] data = {5, 3, 8, 4, 2};
        executeSort(data);
        System.out.println(Arrays.toString(data));
    }
}

挿入ソート

整列済み領域を拡張しながら、未整列要素を適切な位置に挿入するアルゴリズム。

public class InsertionSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int current = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > current) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = current;
        }
    }

    public static void main(String[] args) {
        int[] nums = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6};
        sort(nums);
        System.out.println(Arrays.toString(nums));
    }
}

クイックソート

ピボット要素を選択し、それ以下の値を左側、それより大きい値を右側に分割する再帰的処理。

public class QuickSort {
    public static void partition(int[] arr, int left, int right) {
        if (right - left <= 1) return;
        
        int pivot = arr[left];
        int i = left, j = right - 1;
        
        while (i < j) {
            while (i < right && arr[i] <= pivot) i++;
            while (j >= left && arr[j] > pivot) j--;
            if (i < j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        
        arr[left] = arr[j];
        arr[j] = pivot;
        
        partition(arr, left, j);
        partition(arr, j + 1, right);
    }

    public static void main(String[] args) {
        int[] values = {6, 3, 8, 2, 9, 1};
        partition(values, 0, values.length);
        System.out.println(Arrays.toString(values));
    }
}

マージソート

配列をサブ配列に分割した後、それらをマージしながら整列する分割統治アルゴリズム。

public class MergeSort {
    public static void mergeSort(int[] data, int start, int end) {
        if (end - start <= 1) return;
        
        int mid = (start + end) / 2;
        mergeSort(data, start, mid);
        mergeSort(data, mid, end);
        merge(data, start, mid, end);
    }

    private static void merge(int[] array, int left, int center, int right) {
        int[] temp = new int[right - left];
        int i = left, j = center, k = 0;
        
        while (i < center && j < right) {
            if (array[i] <= array[j]) {
                temp[k++] = array[i++];
            } else {
                temp[k++] = array[j++];
            }
        }
        
        while (i < center) temp[k++] = array[i++];
        while (j < right) temp[k++] = array[j++];
        
        System.arraycopy(temp, 0, array, left, temp.length);
    }

    public static void main(String[] args) {
        int[] dataset = {4, 1, 7, 3, 9, 2};
        mergeSort(dataset, 0, dataset.length);
        System.out.println(Arrays.toString(dataset));
    }
}