Đến nội dung chính
notes.vinhnq.com

Tìm kiếm

Cấu trúc dữ liệu & Thuật toánMid24 phút đọc

Thuật toán cơ bản: Merge sort, Quick sort và cách Java thực sự sắp xếp

Ôn 28 thẻ
Trong bài này

Cụm bài Thuật toán cơ bản: 1. Big-O và sắp xếp O(n²) · 2. Đệ quy và tìm kiếm nhị phân · 3. Merge sort, quick sort

Với một triệu phần tử, các thuật toán O(n²) ở phần 1 cần khoảng 10¹² phép tính, chạy cả tiếng. Bài này dùng chia để trị (divide and conquer: chia bài toán nhỏ ra, giải bằng đệ quy, rồi kết hợp) để đưa về O(n log n) với merge sort và quick sort. Đọc xong, bạn biết Arrays.sort/Collections.sort thực sự dùng thuật toán gì và tránh được các bẫy khi viết Comparator.

1. Merge sort

Ý chính: sắp xếp từng nửa rồi gộp hai nửa đã có thứ tự bằng hai con trỏ. Phần việc nặng nằm ở bước gộp; đổi lại thời gian luôn là O(n log n) và thuật toán stable.

1.1. Ý tưởng

  1. Chia đôi danh sách.
  2. Sắp xếp từng nửa bằng đệ quy. Base case là đoạn 0 hoặc 1 phần tử, vốn đã có thứ tự.
  3. Gộp hai nửa đã sắp xếp thành một.
flowchart TD
  A["38 27 43 3 9 82 10"] --> B["38 27 43 3"]
  A --> C["9 82 10"]
  B --> D["38 27"]
  B --> E["43 3"]
  C --> F["9 82"]
  C --> G["10"]
  D --> D2["27 38"]
  E --> E2["3 43"]
  F --> F2["9 82"]
  D2 --> H["3 27 38 43"]
  E2 --> H
  F2 --> I["9 10 82"]
  G --> I
  H --> J["3 9 10 27 38 43 82"]
  I --> J

1.2. Bước gộp (merge)

Hai con trỏ i, j đứng ở đầu mỗi nửa. Mỗi bước lấy phần tử nhỏ hơn đưa vào kết quả rồi tiến con trỏ đó; một nửa hết thì chép nốt nửa kia. Mỗi phần tử được đụng một lần, nên gộp n phần tử tốn O(n).

Ví dụ gộp [3, 27, 38, 43] và [9, 10, 82]: lấy 3, 9, 10, 27, 38, 43; nửa trái hết thì chép nốt 82.

1.3. Code

static void mergeSort(int[] a) {
    if (a.length < 2) return;
    int[] buf = new int[a.length];             // cấp phát MỘT lần, dùng lại ở mọi tầng
    mergeSort(a, buf, 0, a.length - 1);
}

private static void mergeSort(int[] a, int[] buf, int lo, int hi) {
    if (lo >= hi) return;                      // base case: 0 hoặc 1 phần tử
    int mid = (lo + hi) >>> 1;
    mergeSort(a, buf, lo, mid);
    mergeSort(a, buf, mid + 1, hi);
    if (a[mid] <= a[mid + 1]) return;          // hai nửa đã đúng thứ tự, khỏi gộp
    merge(a, buf, lo, mid, hi);
}

private static void merge(int[] a, int[] buf, int lo, int mid, int hi) {
    System.arraycopy(a, lo, buf, lo, hi - lo + 1);
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi) {
        if (buf[i] <= buf[j]) a[k++] = buf[i++];   // <= (không phải <) để giữ stable
        else a[k++] = buf[j++];
    }
    while (i <= mid) a[k++] = buf[i++];
    while (j <= hi) a[k++] = buf[j++];             // thực ra phần này đã đúng chỗ sẵn
}

Ba chi tiết là điểm cộng khi phỏng vấn:

  • Cấp phát buffer một lần. Tạo mảng tạm mới ở mỗi lần gộp sinh ra O(n log n) rác cho GC.
  • Bỏ qua bước gộp khi a[mid] <= a[mid + 1]: mảng đã sắp xếp chỉ tốn O(n).
  • So sánh bằng <= để khi bằng nhau thì lấy bên trái trước. Đó là thứ làm merge sort stable (giữ nguyên thứ tự của các phần tử bằng nhau).

1.4. Độ phức tạp

T(n) = 2·T(n/2) + c·n: hai bài con một nửa, cộng chi phí gộp tuyến tính. Cây đệ quy có log₂ n tầng, mỗi tầng tổng độ dài các đoạn cần gộp là n, nên tổng là O(n log n).

flowchart TD
  L0["Tầng 0: 1 đoạn n phần tử, gộp tốn n"] --> L1["Tầng 1: 2 đoạn n/2, tổng tốn n"]
  L1 --> L2["Tầng 2: 4 đoạn n/4, tổng tốn n"]
  L2 --> LD["..."]
  LD --> LK["Tầng log n: n đoạn 1 phần tử"]
Merge sort
Tốt nhất / trung bình / xấu nhất O(n log n) cả ba (bản có kiểm tra a[mid] <= a[mid+1] đạt O(n) khi đã sắp xếp)
Bộ nhớ phụ O(n) buffer + O(log n) stack đệ quy
Stable Có
In-place Không (với mảng)

1.5. Merge sort ngoài sách vở

  • Linked list: không cần truy cập ngẫu nhiên, gộp chỉ là nối lại con trỏ nên không cần buffer O(n). Ví dụ điển hình: bài “Sort List” trên LeetCode.
  • Song song hoá: hai nửa độc lập nên dễ chạy song song; Arrays.parallelSort dựa trên ý này (mục 4.3).

2. Quick sort

Ý chính: chọn một pivot (phần tử chốt), dồn phần tử nhỏ hơn sang trái, lớn hơn sang phải, rồi đệ quy hai bên. Nhanh và in-place, nhưng pivot tệ làm nó rơi vào O(n²), nên cái cần học là cách chống worst case.

2.1. Ý tưởng

  1. Chọn pivot X.
  2. Phân hoạch (partition): nhỏ hơn X sang trái, lớn hơn X sang phải. X giờ nằm đúng vị trí K của nó trong mảng đã sắp xếp.
  3. Đệ quy đoạn trái K và đoạn phải K. Không cần bước gộp.
flowchart TD
  A["7 2 9 4 3 8 | pivot = 4"] --> P["partition: 2 3 | 4 | 9 7 8"]
  P --> L["quickSort(2 3)"]
  P --> K["4 đã đúng chỗ"]
  P --> R["quickSort(9 7 8)"]
  L --> L2["2 3"]
  R --> R2["7 8 9"]

2.2. Code: Lomuto partition + pivot ngẫu nhiên

Lomuto partition: một con trỏ quét từ trái sang, gặp phần tử nhỏ hơn pivot thì dồn về đầu đoạn.

static void quickSort(int[] a) {
    quickSort(a, 0, a.length - 1);
}

private static void quickSort(int[] a, int lo, int hi) {
    while (lo < hi) {
        int p = partition(a, lo, hi);
        // đệ quy vào nửa NHỎ hơn, nửa lớn xử lý bằng vòng lặp
        // -> độ sâu stack tối đa O(log n), kể cả khi chia lệch
        if (p - lo < hi - p) {
            quickSort(a, lo, p - 1);
            lo = p + 1;
        } else {
            quickSort(a, p + 1, hi);
            hi = p - 1;
        }
    }
}

private static int partition(int[] a, int lo, int hi) {
    int r = ThreadLocalRandom.current().nextInt(lo, hi + 1);
    swap(a, r, hi);                      // đưa pivot ngẫu nhiên về cuối
    int pivot = a[hi];
    int store = lo;                      // a[lo..store-1] luôn < pivot
    for (int i = lo; i < hi; i++) {
        if (a[i] < pivot) swap(a, i, store++);
    }
    swap(a, store, hi);                  // pivot về đúng vị trí cuối cùng
    return store;
}

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

2.3. Độ phức tạp và worst case

Pivot chia mảng tương đối cân thì có log n tầng, mỗi tầng O(n): trung bình O(n log n) như merge sort. Slide chỉ nói lướt, nhưng phỏng vấn senior chắc chắn hỏi: làm sao tránh worst case?

Vấn đề Cách xử lý
Pivot tệ trên dữ liệu đã sắp xếp Pivot ngẫu nhiên (worst case còn nhưng xác suất cực nhỏ) hoặc median-of-three (trung vị của đầu, giữa, cuối)
Nhiều phần tử trùng nhau Phân hoạch 3 đường (Dutch national flag): < pivot, = pivot, > pivot; đoạn bằng pivot khỏi sort tiếp
Stack đệ quy sâu O(n) khi chia lệch Đệ quy vào nửa nhỏ, lặp với nửa lớn: độ sâu luôn ≤ log₂ n
Kẻ tấn công cố tình tạo input xấu Introsort: vượt độ sâu ~2·log n thì chuyển sang heap sort, đảm bảo O(n log n)
Đoạn nhỏ, overhead đệ quy lớn Dưới vài chục phần tử thì chuyển sang insertion sort
Hoare partition so với Lomuto

2.4. Tính chất

Quick sort
Trung bình O(n log n)
Xấu nhất O(n²) (introsort: O(n log n))
Bộ nhớ phụ O(log n) stack nếu đệ quy vào nửa nhỏ; O(n) nếu cài ngây thơ
Stable Không
In-place Có

3. So sánh các thuật toán sắp xếp

Ý chính: không có thuật toán sắp xếp dựa trên so sánh nào nhanh hơn Ω(n log n) ở trường hợp xấu nhất. Chọn thuật toán là chọn giữa stable, bộ nhớ phụ và độ ổn định của thời gian chạy.

Thuật toán Tốt nhất Trung bình Xấu nhất Bộ nhớ phụ Stable Ghi chú
Bubble O(n) O(n²) O(n²) O(1) Có Chỉ để học
Selection O(n²) O(n²) O(n²) O(1) Không Ít swap nhất
Insertion O(n) O(n²) O(n²) O(1) Có Tốt cho mảng nhỏ / gần sắp xếp
Merge O(n log n) O(n log n) O(n log n) O(n) Có Đảm bảo thời gian, external sort
Quick O(n log n) O(n log n) O(n²) O(log n) Không Nhanh nhất trên thực tế
Heap O(n log n) O(n log n) O(n log n) O(1) Không Đảm bảo + in-place, nhưng không thân thiện cache
Counting / Radix O(n + k) O(n + k) O(n + k) O(n + k) Có Chỉ cho khoá nguyên trong miền nhỏ
TimSort O(n) O(n log n) O(n log n) O(n) Có Mặc định cho object trong Java, Python

Vì sao là Ω(n log n): có n! hoán vị, mỗi phép so sánh cho 1 bit thông tin, nên cần ít nhất log₂(n!) ≈ n log₂ n phép so sánh. Counting sort và radix sort “phá” được giới hạn này vì chúng dùng thẳng giá trị khoá làm chỉ số mảng, không so sánh.

4. Java thực sự sắp xếp như thế nào

Ý chính: Arrays.sort với mảng primitive dùng Dual-Pivot Quicksort; với object (Arrays.sort(Object[]), Collections.sort, List.sort) dùng TimSort. Lý do: primitive không cần stable, object thì cần. Đây là phần đáng giá nhất cho phỏng vấn Java.

4.1. Arrays.sort với mảng primitive: Dual-Pivot Quicksort

  • Từ Java 7, Arrays.sort(int[]) (và long[], double[]…) dùng Dual-Pivot Quicksort của Vladimir Yaroslavskiy. Nó chọn hai pivot P1 ≤ P2, chia mảng làm ba phần < P1, P1..P2, > P2. Nhanh hơn quick sort một pivot, chủ yếu vì ít lần đọc bộ nhớ hơn.
  • Từ Java 14 worst case được đảm bảo O(n log n) (chi tiết trong khối gấp bên dưới).
  • Không stable, nhưng với primitive điều đó không quan trọng: hai số 5 giống hệt nhau, không ai phân biệt được cái nào đứng trước.
Java 14 viết lại Dual-Pivot Quicksort

4.2. Arrays.sort(Object[]), Collections.sort, List.sort: TimSort

TimSort (Java dùng từ Java 7, mượn từ Python của Tim Peters) là thuật toán lai giữa merge sort và insertion sort:

  1. Quét mảng tìm các run: đoạn đã tăng dần sẵn (đoạn giảm dần thì đảo lại).
  2. Run ngắn hơn minrun (JDK khoảng 16 tới 32; Python 32 tới 64) thì kéo dài bằng binary insertion sort.
  3. Gộp các run theo quy tắc trên một stack để luôn cân bằng. Khi một run liên tục “thắng” thì dùng galloping (tìm theo bước nhảy mũ 1, 2, 4, 8…).

Kết quả: stable, tốt nhất O(n) với dữ liệu đã sắp xếp, xấu nhất O(n log n), bộ nhớ phụ tối đa n/2 tham chiếu.

record Order(String customer, int amount) {}

List<Order> orders = new ArrayList<>(List.of(
    new Order("bob", 30), new Order("alice", 10),
    new Order("bob", 10), new Order("alice", 30)));

orders.sort(Comparator.comparingInt(Order::amount));   // lần 1: theo số tiền
orders.sort(Comparator.comparing(Order::customer));    // lần 2: theo khách hàng, stable
// [alice 10, alice 30, bob 10, bob 30]

// gọn hơn, một lần sort với khoá phụ:
orders.sort(Comparator.comparing(Order::customer).thenComparingInt(Order::amount));
  • List.of(...) là bất biến nên sort ném UnsupportedOperationException; vì vậy ví dụ trên bọc trong new ArrayList<>(...).

4.3. Arrays.parallelSort

Chỉ có lợi với mảng lớn khi máy còn core rảnh; trong web service nó tranh tài nguyên với cả ứng dụng.

Ngưỡng song song và ForkJoin common pool

4.4. Bẫy khi viết Comparator

4.5. Sort ở database hay ở ứng dụng?

Xem minh hoạ trực quan

Ý chính: nhập một mảng và xem từng bước chia, gộp, phân hoạch giúp nhớ thuật toán lâu hơn đọc code.

Bài tập

Bài 1: Live coding “Sort an Array”

Đề (diễn đạt lại, LeetCode 912): cho mảng số nguyên, trả về mảng tăng dần, không dùng hàm sort có sẵn, thời gian O(n log n), bộ nhớ phụ càng ít càng tốt. Kích thước tới 5·10⁴, giá trị trong [-5·10⁴, 5·10⁴].

Lời giải Bài 1: merge sort, quick sort 3 đường, counting sort

Lời giải 1: merge sort (code ở mục 1.3).

public int[] sortArray(int[] nums) {
    mergeSort(nums);
    return nums;
}

O(n log n) đảm bảo, O(n) bộ nhớ phụ. An toàn nhất khi đề có test cố tình đánh vào worst case.

Lời giải 2: quick sort 3 đường + pivot ngẫu nhiên (code ở mục 2.3).

public int[] sortArray(int[] nums) {
    quickSort3Way(nums, 0, nums.length - 1);
    return nums;
}

O(n log n) kỳ vọng, O(log n) stack kỳ vọng. Đề có test mảng đã sắp xếp và mảng nhiều phần tử trùng, nên quick sort pivot cố định hoặc Lomuto thuần bị Time Limit Exceeded. Đúng bài học của mục 2.3.

Lời giải 3: counting sort. Miền giá trị chỉ có 10⁵ + 1 giá trị, nên đếm tần suất rồi ghi lại là O(n + k):

public int[] sortArray(int[] nums) {
    final int OFFSET = 50_000;
    int[] count = new int[2 * OFFSET + 1];
    for (int x : nums) count[x + OFFSET]++;
    int k = 0;
    for (int v = 0; v < count.length; v++)
        while (count[v]-- > 0) nums[k++] = v - OFFSET;
    return nums;
}

Mình đã chạy merge sort và hai bản quick sort với 2.000 mảng ngẫu nhiên (đối chiếu với Arrays.sort), mảng một triệu phần tử đã sắp xếp và mảng một triệu phần tử giống hệt nhau.

Bài 2 (tự đặt): Sắp xếp theo nhiều khoá

Đề: cho danh sách nhân viên (department, salary, name), sắp xếp theo phòng ban tăng dần, cùng phòng thì lương giảm dần, cùng lương thì theo tên.

Lời giải Bài 2
record Employee(String department, long salary, String name) {}

employees.sort(Comparator.comparing(Employee::department)
        .thenComparing(Employee::salary, Comparator.reverseOrder())
        .thenComparing(Employee::name, Comparator.nullsLast(Comparator.naturalOrder())));

Ghi nhớ

  • Giải thích được vì sao merge sort luôn O(n log n) bằng cây đệ quy, và chi tiết nào làm nó stable.
  • Kể được các trường hợp quick sort rơi vào O(n²) và cách chống từng trường hợp.
  • Giải thích được giới hạn Ω(n log n) và vì sao counting sort vượt qua được.
  • Biết Arrays.sort dùng thuật toán gì cho primitive và cho object, và vì sao khác nhau.
  • Nhận ra được comparator nguy hiểm (a - b, vi phạm contract, null) và biết khi nào nên sort ở database.

Câu hỏi phỏng vấn

Junior

Merge sort hoạt động thế nào? Độ phức tạp?

Chia đôi, sort đệ quy từng nửa, gộp bằng hai con trỏ; O(n log n) trong mọi trường hợp.

Có log n tầng, mỗi tầng gộp tốn O(n). Cần O(n) bộ nhớ phụ và là stable.

Quick sort hoạt động thế nào? Khi nào rơi vào O(n²)?

Chọn pivot, phân hoạch nhỏ sang trái lớn sang phải, rồi đệ quy hai bên. Rơi vào O(n²) khi pivot liên tục là min hoặc max.

Sau phân hoạch pivot nằm đúng chỗ. Ví dụ worst case: lấy phần tử đầu làm pivot trên mảng đã sắp xếp.

Merge sort và quick sort khác nhau ở đâu?

Merge sort chia dễ, gộp khó; quick sort chia khó (partition), không cần gộp.

Merge sort stable, đảm bảo O(n log n), tốn O(n) bộ nhớ. Quick sort in-place, thường nhanh hơn trên thực tế, không stable, worst case O(n²).

Mid

Làm sao tránh worst case của quick sort?

Pivot ngẫu nhiên hoặc median-of-three, cộng introsort để đảm bảo O(n log n).

  • Phân hoạch 3 đường khi có nhiều phần tử trùng.
  • Đệ quy vào nửa nhỏ để giới hạn stack O(log n).
  • Theo kiểu introsort, chuyển sang heap sort khi đệ quy quá sâu.
Arrays.sort(int[]) và Arrays.sort(Object[]) dùng thuật toán gì? Vì sao khác nhau?

Primitive dùng Dual-Pivot Quicksort, object dùng TimSort, vì object cần stable còn primitive thì không.

Dual-Pivot Quicksort có từ Java 7, viết lại ở Java 14 với fallback heap sort. Primitive bằng nhau không phân biệt được, nên chọn thuật toán nhanh và in-place. Object có nhiều trường và người dùng hay sort nhiều lần theo các khoá khác nhau.

Vì sao (a, b) -> a - b là comparator nguy hiểm?

Phép trừ có thể tràn số, làm comparator trả sai dấu.

Integer.MIN_VALUE - 1 thành số dương, nên kết quả sort sai hoặc TimSort ném “Comparison method violates its general contract!”. Dùng Integer.compare hoặc Comparator.comparingInt.

Giới hạn dưới của sắp xếp dựa trên so sánh là gì? Counting sort vượt qua bằng cách nào?

Ω(n log n); counting sort không so sánh mà dùng giá trị khoá làm chỉ số, nên đạt O(n + k).

Phải phân biệt n! hoán vị, mỗi phép so sánh cho 1 bit, cần log₂(n!) ≈ n log n phép. Counting/radix sort chỉ áp dụng cho khoá nguyên trong miền nhỏ (hoặc chia được thành chữ số).

Senior

TimSort hoạt động thế nào và vì sao nó hợp với dữ liệu thật?

TimSort tìm các run đã có thứ tự rồi gộp chúng; dữ liệu thật thường đã có thứ tự cục bộ nên nó gần O(n).

Run giảm dần thì đảo lại; run ngắn được kéo dài tới minrun bằng binary insertion sort. Các run được gộp theo bất biến trên một stack để luôn cân bằng; khi một phía thắng liên tục thì chuyển sang galloping. Dữ liệu append theo thời gian hay list gần sắp xếp chạy gần O(n), mà vẫn đảm bảo O(n log n) và stable.

Cần sắp xếp file 100 GB trên máy 8 GB RAM. Làm thế nào?

External merge sort: sort từng khối vừa RAM ra file tạm, rồi k-way merge bằng min-heap.

  • Đọc khối ~1 GB, sort trong bộ nhớ, ghi ra file tạm (khoảng 100 run).
  • Mở tất cả run, PriorityQueue giữ phần tử đầu mỗi run; lấy min ghi ra output, nạp phần tử kế tiếp của run đó.
  • Đọc/ghi tuần tự với buffer lớn. Quá nhiều run thì gộp nhiều lượt.

Database cũng xử lý ORDER BY tràn bộ nhớ sort theo cách này.

Lỗi “Comparison method violates its general contract!” là gì và debug thế nào?

TimSort phát hiện comparator không nhất quán: không đối xứng, không bắc cầu, hoặc kết quả đổi trong lúc sort.

  • Nguyên nhân hay gặp: phép trừ bị tràn, xử lý null/NaN sai, so sánh dữ liệu bị luồng khác sửa đồng thời, comparator dựa trên thời gian/random.
  • Chỉ lộ ra với dữ liệu đủ lớn nên thường thấy ở production.
  • Sửa: viết bằng Comparator.comparing..., kiểm tra contract bằng property-based test, sort trên snapshot bất biến.

Flag java.util.Arrays.useLegacyMergeSort chỉ che giấu lỗi, không sửa.

Có nên dùng Arrays.parallelSort trong một web service không?

Thường là không; nó chạy trên ForkJoin common pool dùng chung, nên dưới tải cao có thể làm tăng latency của request khác.

Chỉ có lợi với mảng rất lớn (vượt xa ngưỡng 8192) và khi máy còn core rảnh. Service nhiều request đồng thời thì core vốn đã bận, sort tuần tự thường tốt hơn; job batch thì parallelSort hợp lý. Luôn đo bằng benchmark.

Cần lấy top 100 sản phẩm bán chạy nhất từ luồng 10 triệu bản ghi. Có cần sort toàn bộ không?

Không. Dùng min-heap kích thước 100: O(n log k) thời gian, O(k) bộ nhớ, chạy được dạng streaming.

Duyệt từng bản ghi, lớn hơn đỉnh heap thì thay đỉnh. Dữ liệu trong DB thì ORDER BY sales DESC LIMIT 100 với index phù hợp. Toàn bộ dữ liệu đã nằm trong mảng thì quickselect cho O(n) trung bình.

Từ vựng tiếng Anh

Term Phát âm Nghĩa Ví dụ câu trong phỏng vấn
divide and conquer /dɪˈvaɪd ənd ˈkɑːŋkər/ chia để trị “Both merge sort and quicksort are divide-and-conquer algorithms.”
merge /mɜːrdʒ/ gộp “Merging two sorted halves takes linear time.”
pivot /ˈpɪvət/ phần tử chốt “A random pivot makes the worst case very unlikely.”
partition /pɑːrˈtɪʃən/ phân hoạch “After partitioning, the pivot is in its final position.”
three-way partitioning /θriː weɪ pɑːrˈtɪʃənɪŋ/ phân hoạch ba đường “Three-way partitioning handles lots of duplicate keys.”
recursion depth /rɪˈkɜːrʒən dɛpθ/ độ sâu đệ quy “Recursing into the smaller side bounds the recursion depth to log n.”
run /rʌn/ đoạn đã có thứ tự “TimSort detects natural runs in the input.”
lower bound /ˈloʊər baʊnd/ cận dưới “Comparison sorts have an n log n lower bound.”
external sort /ɪkˈstɜːrnəl sɔːrt/ sắp xếp ngoài “For data larger than RAM we’d use an external merge sort.”
k-way merge /keɪ weɪ mɜːrdʒ/ gộp k đường “A k-way merge uses a min-heap over the heads of each run.”
comparator contract /kəmˈpærətər ˈkɑːntrækt/ ràng buộc của comparator “Breaking the comparator contract can make TimSort throw.”
top-k /tɑːp keɪ/ k phần tử lớn nhất “For top-k we don’t need a full sort, just a bounded heap.”

Ghi chép dựa trên khoá Fundamentals of Backend (Ronin Engineer), viết lại theo cách hiểu của mình.