Sorting.java

import java.util.Arrays;
import java.util.Random;

/**
 * Lab 主題二：排序（sorting）。
 *
 * 任何「就地」（in-place）排序都必須滿足兩個後置條件：
 *   1. 執行後陣列是遞增排序的；
 *   2. 執行後的陣列是原本元素的一個「排列」（沒有多、沒有少、沒有變）。
 * 很多人只記得第 1 條，忘了第 2 條！
 *
 * 編譯與執行：javac Sorting.java && java -ea Sorting
 */
public class Sorting {

    // 用來計算「比較次數」，方便比較演算法的效率
    static long comparisons = 0;

    static boolean less(int x, int y) {
        comparisons = comparisons + 1;
        return x < y;
    }

    static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    /** 選擇排序：每回合從「未排序區」挑出最小值，換到未排序區的最前面。O(n^2) */
    static void selectionSort(int[] arr) {
        int i = 0;
        while (i < arr.length) {
            // INV: arr[0..i-1] 已排序，且都 <= arr[i..] 的每個元素
            int minPos = i;
            int j = i + 1;
            while (j < arr.length) {
                if (less(arr[j], arr[minPos])) {
                    minPos = j;
                }
                j = j + 1;
            }
            swap(arr, i, minPos);
            i = i + 1;
        }
    }

    /** 氣泡排序（含提前結束）：相鄰兩兩比較，把最大值一路「冒」到尾端。O(n^2)，已排序時 O(n) */
    static void bubbleSort(int[] arr) {
        int end = arr.length - 1;
        while (end > 0) {
            // INV: arr[end+1..] 已排序，且都 >= arr[0..end] 的每個元素
            boolean swapped = false;
            int j = 0;
            while (j < end) {
                if (less(arr[j + 1], arr[j])) {
                    swap(arr, j, j + 1);
                    swapped = true;
                }
                j = j + 1;
            }
            if (!swapped) {
                return;              // 整趟都沒交換：已經排好了，提前結束
            }
            end = end - 1;
        }
    }

    /** 插入排序：把下一個元素「插入」已排序區的正確位置。O(n^2)，已排序時 O(n) */
    static void insertionSort(int[] arr) {
        int i = 1;
        while (i < arr.length) {
            // INV: arr[0..i-1] 已排序
            int x = arr[i];
            int j = i - 1;
            while (j >= 0 && less(x, arr[j])) {
                arr[j + 1] = arr[j];     // 比 x 大的元素往右挪一格
                j = j - 1;
            }
            arr[j + 1] = x;              // 放進空出來的位置
            i = i + 1;
        }
    }

    /**
     * 合併兩個「已排序」的陣列成一個已排序的新陣列。
     * 只需各走訪一次：O(left.length + right.length)。
     */
    static int[] merge(int[] left, int[] right) {
        int[] out = new int[left.length + right.length];
        int i = 0, j = 0, k = 0;
        while (i < left.length && j < right.length) {
            if (!less(right[j], left[i])) {      // left[i] <= right[j]：取左邊（相等取左邊 → 穩定）
                out[k] = left[i];
                i = i + 1;
            } else {
                out[k] = right[j];
                j = j + 1;
            }
            k = k + 1;
        }
        while (i < left.length) {                // 左邊剩下的直接搬過來
            out[k] = left[i];
            i = i + 1;
            k = k + 1;
        }
        while (j < right.length) {               // 右邊剩下的直接搬過來
            out[k] = right[j];
            j = j + 1;
            k = k + 1;
        }
        return out;
    }

    /** 合併排序（分治法）：切半 → 遞迴排序兩半 → 合併。O(n log n)，但需要 O(n) 額外空間 */
    static int[] mergeSort(int[] input, int start, int end) {
        if (end < start) {                       // 基底：空範圍
            return new int[]{};
        }
        if (end == start) {                      // 基底：單一元素本身就是排好的
            return new int[]{input[start]};
        }
        int mid = (start + end) / 2;             // Divide
        int[] left = mergeSort(input, start, mid);      // Conquer
        int[] right = mergeSort(input, mid + 1, end);
        return merge(left, right);               // Combine
    }

    /** 對外版本：讓合併排序也符合 sort(int[]) 的「就地」契約（把結果複製回原陣列）。 */
    static void mergeSort(int[] arr) {
        int[] sorted = mergeSort(arr, 0, arr.length - 1);
        System.arraycopy(sorted, 0, arr, 0, arr.length);
    }

    static boolean isSorted(int[] arr) {
        int i = 0;
        while (i < arr.length - 1) {
            if (arr[i] > arr[i + 1]) {
                return false;
            }
            i = i + 1;
        }
        return true;
    }

    // ---------- 測試 ----------

    /** 排序演算法的介面（函式介面）：讓測試程式可以「把演算法當參數傳」。 */
    interface Sorter {
        void sort(int[] arr);
    }

    static void checkSorter(String name, Sorter sorter) {
        int[][] cases = {
            {},                              // 空陣列
            {42},                            // 單一元素
            {7, 7},                          // 兩個相同
            {1, 2, 3, 4, 5, 6, 7, 8, 9},     // 已排序
            {9, 8, 7, 6, 5, 4, 3, 2, 1},     // 反向排序
            {6, -5, 212, 42, 19, 0, 0, 5, 9718},   // 隨機（含負數與重複）
            {-1, -2, -3, -4, -5},
        };
        for (int[] original : cases) {
            int[] toSort = original.clone();
            int[] expected = original.clone();
            Arrays.sort(expected);                       // 用標準函式庫的答案當「標準答案」
            sorter.sort(toSort);
            assert isSorted(toSort) : name + " 後置條件 1 失敗：" + Arrays.toString(toSort);
            assert Arrays.equals(toSort, expected)       // 同時檢查後置條件 2（是原元素的排列）
                    : name + " 後置條件 2 失敗：" + Arrays.toString(toSort);
        }
        System.out.println("  " + name + "：" + cases.length + " 組測試通過");
    }

    static void countComparisons(String name, Sorter sorter, int[] data) {
        int[] copy = data.clone();
        comparisons = 0;
        sorter.sort(copy);
        System.out.printf("  %-14s 比較次數 = %,d%n", name, comparisons);
    }

    public static void main(String[] args) {
        System.out.println("=== 正確性測試 ===");
        checkSorter("selectionSort", Sorting::selectionSort);
        checkSorter("bubbleSort", Sorting::bubbleSort);
        checkSorter("insertionSort", Sorting::insertionSort);
        checkSorter("mergeSort", Sorting::mergeSort);

        int n = 2000;
        int[] random = new Random(42).ints(n, 0, 100_000).toArray();
        int[] sorted = random.clone();
        Arrays.sort(sorted);
        int[] reversed = new int[n];
        for (int i = 0; i < n; i++) {
            reversed[i] = sorted[n - 1 - i];
        }

        System.out.println("=== 比較次數（n = " + n + "，隨機資料）===");
        countComparisons("selectionSort", Sorting::selectionSort, random);
        countComparisons("bubbleSort", Sorting::bubbleSort, random);
        countComparisons("insertionSort", Sorting::insertionSort, random);
        countComparisons("mergeSort", Sorting::mergeSort, random);

        System.out.println("=== 比較次數（n = " + n + "，已排序資料：最佳情況）===");
        countComparisons("selectionSort", Sorting::selectionSort, sorted);
        countComparisons("bubbleSort", Sorting::bubbleSort, sorted);
        countComparisons("insertionSort", Sorting::insertionSort, sorted);
        countComparisons("mergeSort", Sorting::mergeSort, sorted);

        System.out.println("=== 比較次數（n = " + n + "，反向排序：最差情況）===");
        countComparisons("selectionSort", Sorting::selectionSort, reversed);
        countComparisons("bubbleSort", Sorting::bubbleSort, reversed);
        countComparisons("insertionSort", Sorting::insertionSort, reversed);
        countComparisons("mergeSort", Sorting::mergeSort, reversed);
        System.out.println("全部通過。");
    }
}