Sorting: chọn thuật toán bằng constraint

Đổi mỗi constraint thành một điều cần kiểm chứng

Trước khi chọn tên thuật toán, viết một câu mô tả workload: “Tôi có n records, khóa so sánh là …, cần giữ thứ tự khi bằng khóa hay không, được phép sửa input hay không, có … bộ nhớ phụ và cần … giới hạn worst case.” Đây là mẫu trả lời, không phải giả định mặc định cho mọi bài toán.

Phân biệt đúng thứ tự, giữ đủ dữ liệu và đáp ứng tài nguyên. Một output nhìn đã sorted vẫn sai nếu làm mất duplicate; một thuật toán đúng vẫn không phù hợp nếu vượt RAM hoặc làm tăng latency của request khác. Các bài practice bên dưới yêu cầu evidence cho từng phần.

Không đọc Big-O tách khỏi implementation

Quy ước: n là số phần tử; k trong counting/radix là kích thước miền key hoặc radix; d là số pass/digit. k trong bài top-K ở dưới là số kết quả cần giữ, không phải miền key.

• Quick sort: O(log n) stack là trường hợp trung bình/cân bằng. Bản đệ quy hai nhánh có thể cần O(n) stack khi partition lệch liên tục. “In-place” trong cách gọi thông dụng không xóa chi phí stack. [R9]
• Counting sort: O(k) trong bảng là bộ đếm. Bản stable phân phối records sang output array còn cần O(n), nên tổng bộ nhớ phụ thường là O(n + k). Không được suy ra “stable counting sort cho records chỉ cần O(k)” từ dòng tóm tắt. [R10]
• Radix sort: điều kiện mỗi pass stable đặc biệt quan trọng với LSD. Cần định nghĩa cách xử lý dấu, độ dài key và alphabet; cách sort byte của số âm không thể bỏ qua bit dấu. [R10]
• Merge/heap: ký hiệu O(n log n) trong bảng là upper bound của các phiên bản được xét, không phải lời khẳng định Θ(n log n) cho mọi input và mọi biến thể. Merge sort nguồn vẫn thực hiện merge ở mỗi mức; biến thể adaptive có thể bỏ việc thừa. [R8]

Suy luận về lower bound: trường hợp tổng quát với n key phân biệt phải phân biệt n! hoán vị; decision tree nhị phân cần độ sâu ít nhất log₂(n!). Vì vậy không mâu thuẫn khi một input đã sorted được xử lý tuyến tính, hoặc khi counting/radix khai thác cấu trúc key thay vì chỉ hỏi “nhỏ hơn hay lớn hơn”.

Equal theo comparator, không phải theo identity

Ví dụ tự xây dựng: mỗi record có (key, id), nhưng comparator chỉ đọc key. Sau stable sort, A vẫn đứng trước B:

Input:        [(2, A), (1, X), (2, B)]
Stable sort:  [(1, X), (2, A), (2, B)]

Với multi-pass sorting, sort khóa phụ trước rồi stable-sort khóa chính: ví dụ theo tên trước, theo phòng ban sau như nguồn. Nếu thêm ID vào comparator, các record cùng business key nhưng khác ID không còn “equal” đối với toàn comparator. Stability và deterministic tie-breaker giải quyết hai yêu cầu khác nhau. [R3]

Đề xuất contract: ghi rõ “sort tại chỗ” hay “trả bản sao đã sort”. Trả bản sao không đồng nghĩa bản sao đó immutable. Trong runner, sortedCopy bảo toàn input nhưng kết quả vẫn là một int[] có thể sửa; test kiểm đúng lời hứa này.

Invariant, buffer và cách gọi đúng

Trước vòng merge, hai đoạn [left, mid] và [mid + 1, right] đã sorted. Mỗi bước lấy phần tử nhỏ hơn ở đầu hai đoạn; khi bằng nhau lấy bên trái trước. Quy tắc này bảo toàn thứ tự của các phần tử bằng khóa qua mỗi lần merge.

Hàm nội bộ giả định array và buffer khác nhau, buffer đủ dài và chỉ số hợp lệ. Cách gọi toàn mảng dưới đây cấp một buffer duy nhất; với mảng rỗng, right = -1 và base case trả về ngay.

int[] data = {3, -1, 3, Integer.MIN_VALUE};
int[] buffer = new int[data.length];
mergeSort(data, 0, data.length - 1, buffer);

Suy ra từ implementation này: thời gian O(n log n), buffer O(n), stack O(log n); tổng auxiliary space vẫn O(n). Không cấp buffer mới cho từng recursive call. Nếu tự chuyển sang records, test stability bằng ID/ordinal; hai số nguyên cùng giá trị không đủ để quan sát identity bị đảo. Nền tảng divide–sort–merge được đối chiếu tại [R8].

Lomuto partition: phần nào đã đúng?

Trong vòng lặp, [low, boundary) chứa giá trị nhỏ hơn pivot; [boundary, i) chứa giá trị lớn hơn hoặc bằng pivot; phần từ i đến trước high chưa xét. Cuối vòng lặp, swap đưa pivot vào vị trí boundary. Ví dụ [3, 1, 3, 2] cho [1, 2, 3, 3] và pivot index bằng 1.

Phạm vi biện pháp: random pivot cải thiện expected behavior, median-of-three là heuristic, không phải hard worst-case guarantee; với nhiều duplicate, 3-way partition tách riêng vùng bằng pivot. Introsort dùng fallback để chặn degeneration. Đừng gán worst case của đoạn Lomuto trên cho mọi hybrid sort. [R9] [R5]

Source chỉ cung cấp partition, chưa phải một quick sort hoàn chỉnh. Runner ở phần Practice bổ sung swap, wrapper và hai lời gọi đệ quy trên [low, p−1], [p+1, high]; không sort lại pivot.

API contract khác implementation note

Phần tóm tắt BK được giữ ở trên; các caveat sau hiệu chỉnh cách hiểu “primitive arrays” và “parallelSort”. Java API cho phép thay thuật toán miễn là giữ contract: stability của object sort là guarantee, còn tên thuật toán không phải lời hứa bất biến giữa các bản JDK. [R1]

Đề xuất đo lường: benchmark chính overload, JDK build, data type, distribution và mức tải CPU sẽ dùng thật. Ghi cả memory/allocation và tác động lên workload khác; đừng dùng kết quả chạy riêng để cam kết latency khi common pool đang bận. Quy trình đo nằm ở Practice 3.

Không có exception chưa có nghĩa comparator đúng

Contract gồm đối xứng dấu khi đảo đối số, transitivity, và tính nhất quán với phần tử thứ ba khi hai phần tử compare bằng 0. Không bắt buộc compare-bằng-0 luôn đồng nghĩa equals. Việc sort phát hiện vi phạm và ném IllegalArgumentException là tùy chọn, không phải validator đầy đủ. [R3] [R2]

Ví dụ tự xây dựng: MAX_VALUE > 0 và 0 > −1, nhưng phép trừ MAX_VALUE − (−1) tràn thành số âm. Runner kiểm witness này trực tiếp, rồi kiểm các luật trên comparator dùng Integer.compare; không chờ library phải ném lỗi. Quy tắc overflow tham chiếu tại [R12].

Giả định của code Employee: team, salary, id không null; salary là BigDecimal; ID duy nhất trong dataset. Thứ tự là team tăng, salary giảm, ID tăng. Với dữ liệu thật có null, định nghĩa chính sách null tường minh trước khi sort. [R3]

Suy luận thiết kế: unique tie-breaker tạo thứ tự xác định trên cùng một snapshot. Nó không tự ngăn việc chèn/xóa records giữa hai lần gọi API gây lệch pagination; cần mô tả cả snapshot/cursor policy và không đổi sort keys trong lúc so sánh.

Năm mục trên giữ nguyên mục tiêu nguồn. Các acceptance gate dưới đây làm rõ cách chứng minh đã hoàn thành; không tăng số lượng bài practice.

Runner tự chứa · SortingLab.java

Copy nguyên khối sau vào SortingLab.java, chạy bằng JDK 21. Chỉ dùng Java standard library. Ba sample nguồn được giữ ở trên; runner bổ sung class, imports, dữ liệu Employee, swap, wrappers và assertions để các đoạn đó chạy được.

import java.math.BigDecimal;
import java.util.*;
import java.util.function.Consumer;

public final class SortingLab {
    private static int sortChecks;
    private static int copyChecks;
    private static int topKChecks;

    static void mergeSort(int[] a, int left, int right, int[] buffer) {
        if (left >= right) return;
        int mid = left + (right - left) / 2;
        mergeSort(a, left, mid, buffer);
        mergeSort(a, mid + 1, right, buffer);

        int i = left, j = mid + 1, k = left;
        while (i <= mid && j <= right) {
            buffer[k++] = a[i] <= a[j] ? a[i++] : a[j++];
        }
        while (i <= mid) buffer[k++] = a[i++];
        while (j <= right) buffer[k++] = a[j++];
        System.arraycopy(buffer, left, a, left, right - left + 1);
    }

    static int partition(int[] a, int low, int high) {
        int pivot = a[high];
        int boundary = low;
        for (int i = low; i < high; i++) {
            if (a[i] < pivot) swap(a, i, boundary++);
        }
        swap(a, boundary, high);
        return boundary;
    }

    static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    static void merge(int[] a) {
        Objects.requireNonNull(a, "a");
        mergeSort(a, 0, a.length - 1, new int[a.length]);
    }

    // Teaching version: last pivot, recursive Lomuto; not a production default.
    static void quick(int[] a) {
        Objects.requireNonNull(a, "a");
        quickSort(a, 0, a.length - 1);
    }

    static void quickSort(int[] a, int low, int high) {
        if (low >= high) return;
        int p = partition(a, low, high);
        quickSort(a, low, p - 1);
        quickSort(a, p + 1, high);
    }

    static void insertionSort(int[] a) {
        Objects.requireNonNull(a, "a");
        for (int i = 1; i < a.length; i++) {
            int value = a[i], j = i - 1;
            while (j >= 0 && a[j] > value) {
                a[j + 1] = a[j];
                j--;
            }
            a[j + 1] = value;
        }
    }

    // Non-mutating API: a new array, not an immutable returned array.
    static int[] sortedCopy(int[] input) {
        Objects.requireNonNull(input, "input");
        int[] copy = input.clone();
        merge(copy);
        return copy;
    }

    // Largest k VALUES, with multiplicities, descending; k == 0 consumes nothing.
    static int[] largestK(PrimitiveIterator.OfInt input, int k) {
        Objects.requireNonNull(input, "input");
        if (k < 0) throw new IllegalArgumentException("k must be nonnegative");
        if (k == 0) return new int[0];
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        while (input.hasNext()) {
            int value = input.nextInt();
            if (heap.size() < k) {
                heap.offer(value);
            } else if (value > heap.peek()) {
                heap.poll();
                heap.offer(value);
            }
        }
        int[] result = new int[heap.size()];
        for (int i = result.length - 1; i >= 0; i--) {
            result[i] = heap.remove();
        }
        return result;
    }

    static Map<Integer, Integer> multiset(int[] a) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int value : a) counts.merge(value, 1, Integer::sum);
        return counts;
    }

    static void check(boolean condition, String message) {
        if (!condition) throw new AssertionError(message);
    }

    static void verify(int[] input) {
        int[] expected = input.clone();
        Arrays.sort(expected);
        List<Consumer<int[]>> sorts = List.of(
            SortingLab::insertionSort, SortingLab::merge, SortingLab::quick);
        for (Consumer<int[]> sort : sorts) {
            int[] actual = input.clone();
            sort.accept(actual);
            check(Arrays.equals(actual, expected), "oracle mismatch");
            for (int i = 1; i < actual.length; i++) {
                check(actual[i - 1] <= actual[i], "not nondecreasing");
            }
            check(multiset(actual).equals(multiset(input)), "multiset changed");
            sortChecks++;
        }

        int[] before = input.clone();
        int[] copy = sortedCopy(input);
        check(Arrays.equals(before, input), "input mutated");
        check(copy != input && Arrays.equals(copy, expected), "copy contract");
        copyChecks++;

        for (int k : new int[] {0, 1, 3, 100}) {
            int[] actual = largestK(Arrays.stream(input).iterator(), k);
            int[] wanted = new int[Math.min(k, input.length)];
            for (int i = 0; i < wanted.length; i++) {
                wanted[i] = expected[expected.length - 1 - i];
            }
            check(Arrays.equals(actual, wanted), "top-k mismatch");
            topKChecks++;
        }
    }

    record Item(int key, String id) {}
    record Employee(String team, BigDecimal salary, String id) {}

    static void verifyBusinessSorting() {
        List<Item> items = new ArrayList<>(List.of(
            new Item(2, "A"), new Item(1, "X"), new Item(2, "B")));
        items.sort(Comparator.comparingInt(Item::key));
        check(items.stream().map(Item::id).toList().equals(
            List.of("X", "A", "B")), "stable order lost");

        List<Employee> employees = new ArrayList<>(List.of(
            new Employee("A", new BigDecimal("20"), "E2"),
            new Employee("B", new BigDecimal("50"), "E3"),
            new Employee("A", new BigDecimal("20"), "E1"),
            new Employee("A", new BigDecimal("30"), "E4")));
        Comparator<Employee> byTeamThenSalary =
            Comparator.comparing(Employee::team)
                      .thenComparing(Employee::salary, Comparator.reverseOrder())
                      .thenComparing(Employee::id); // deterministic tie-breaker

        employees.sort(byTeamThenSalary);
        check(employees.stream().map(Employee::id).toList().equals(
            List.of("E4", "E1", "E2", "E3")), "tie-breaker mismatch");

        String[] backing = {"b", "a"};
        Arrays.asList(backing).sort(Comparator.naturalOrder());
        check(backing[0].equals("a"), "backing array not changed");
        boolean rejected = false;
        try {
            List.of(2, 1).sort(Integer::compare);
        } catch (UnsupportedOperationException expected) {
            rejected = true;
        }
        check(rejected, "unmodifiable list accepted sort");
    }

    static void verifyComparator() {
        Comparator<Integer> bad = (a, b) -> a - b;
        int x = Integer.MAX_VALUE, y = 0, z = -1;
        check(bad.compare(x, y) > 0 && bad.compare(y, z) > 0
            && bad.compare(x, z) < 0, "expected transitivity witness");
        // A sorting method need not detect every invalid comparator.
        Comparator<Integer> good = Integer::compare;
        int[] values = {Integer.MIN_VALUE, -1, 0, 1, Integer.MAX_VALUE};
        for (int a : values) for (int b : values) for (int c : values) {
            int ab = good.compare(a, b), bc = good.compare(b, c);
            check(Integer.signum(ab) == -Integer.signum(good.compare(b, a)),
                "sign symmetry");
            if (ab > 0 && bc > 0) check(good.compare(a, c) > 0, "transitivity");
            if (ab == 0) check(Integer.signum(good.compare(a, c))
                == Integer.signum(good.compare(b, c)), "zero consistency");
        }
    }

    public static void main(String[] args) {
        int[][] edges = {
            {}, {7}, {1, 2, 3, 4}, {4, 3, 2, 1}, {2, 2, 2, 2},
            {3, 1, 3, -1, 1}, {Integer.MAX_VALUE, 0, Integer.MIN_VALUE, -1},
            {1, 2, 4, 3, 5}
        };
        for (int[] edge : edges) verify(edge);
        Random random = new Random(1729);
        for (int trial = 0; trial < 300; trial++) {
            int[] input = new int[random.nextInt(129)];
            for (int i = 0; i < input.length; i++) {
                input[i] = trial % 2 == 0 ? random.nextInt(9) - 4 : random.nextInt();
            }
            verify(input);
        }
        verifyBusinessSorting();
        verifyComparator();
        boolean rejected = false;
        try {
            largestK(Arrays.stream(new int[] {1}).iterator(), -1);
        } catch (IllegalArgumentException expected) {
            rejected = true;
        }
        check(rejected, "negative k accepted");
        System.out.printf("PASS sorts=%d copy=%d topK=%d%n",
            sortChecks, copyChecks, topKChecks);
        System.out.println("PASS stability comparator mutability negative-k");
    }
}

javac -encoding UTF-8 SortingLab.java
java -ea SortingLab

PASS sorts=924 copy=308 topK=1232
PASS stability comparator mutability negative-k

924 lượt sort = 308 datasets × 3 thuật toán; 308 datasets = 8 edge cases + 300 generated cases; 1.232 lượt top-K = 308 × 4 giá trị k. Không có số liệu latency/throughput trong output này. Stability test trong runner kiểm List.sort; để kiểm một merge sort cho records do bạn tự viết, cần bổ sung bản tagged-record riêng.