Sắp xếp & thứ tự: tổng kết và cheat sheet

TL;DR: Module này đi từ cận dưới Ω(n log n) của comparison sort, qua tự cài Merge, Quick và Heap sort, tới external merge sort cho dữ liệu vượt RAM và đọc source TimSort cùng Redis ZSET. Trang này là cheat sheet để bookmark: bảng so sánh 9 thuật toán, glossary 15 thuật ngữ, 5 bẫy thực tế và 4 câu tự kiểm tra.

Đã đi qua những gì

Từ tổng quan module, bạn đã học:

• Sort landscape: 5 thuộc tính phân loại (stable, in-place, adaptive, online, comparison-based) và chứng minh cận dưới Ω(n log n) bằng cây quyết định.
• Quadratic sorts: Insertion sort chạy O(n) khi dữ liệu gần như đã sắp xếp nên TimSort dùng nó cho đoạn ngắn; Selection sort ít swap nhất; Bubble sort chỉ để học.
• Merge sort: O(n log n) ở mọi trường hợp và stable, đổi lại tốn buffer O(n); k-way merge là nền của external sort.
• Quick sort: trung bình O(n log n) với hằng số nhỏ nhờ tận dụng cache; worst case O(n²) tránh bằng pivot ngẫu nhiên hoặc median-of-three.
• Heap sort: heap, build-heap O(n), heapsort in-place O(n log n) nhưng chậm hơn Quick sort vì cache miss.
• Counting, Radix, Bucket sort: vượt qua Ω(n log n) bằng cách dùng thông tin về key, đổi lại phải biết trước cấu trúc của key.
• Skip list: tập có thứ tự dựa trên xác suất, search và insert O(log n) kỳ vọng, không cần phép xoay.
• Mini-challenge External merge sort: sort file vượt RAM bằng chunk và min-heap.
• Case study TimSort và Redis ZSET: cách nhận ra run, galloping, merge stack; ZSET ghép skip list với dict.

Cheat sheet

Bảng so sánh 9 thuật toán sắp xếp

*Bucket sort stable khi dùng stable sort bên trong mỗi bucket.

Quy tắc chọn algorithm

External merge sort: skeleton

function externalMergeSort(inputFile, outputFile, chunkSize):
    -- Pha 1: Tạo sorted run
    chunks <- []
    while inputFile không hết:
        data <- đọc chunkSize phần tử vào RAM
        sort(data)                         -- sort trong RAM bằng thuật toán bất kỳ
        chunkFile <- ghi data ra file tạm
        chunks.append(chunkFile)

    -- Pha 2: k-way merge
    H <- MinHeap                           -- mỗi entry: (giá trị, chunk_index)
    for each chunk trong chunks:
        H.push((chunk.readNext(), chunk))  -- lấy phần tử đầu mỗi chunk
    while H không rỗng:
        (val, chunk) <- H.pop()
        ghi val ra outputFile
        if chunk còn phần tử:
            H.push((chunk.readNext(), chunk))

// Time: O(n log n)  Space: O(k) RAM cho heap, n/k cho mỗi chunk buffer

Glossary module

Bẫy thường gặp

Bẫy 1: Dùng Counting sort khi k quá lớn. Counting sort O(n+k) hiệu quả khi k (khoảng giá trị của key) nhỏ so với n. Nếu sort 1000 số nguyên trong khoảng [0, 10^9], mảng đếm cần 10^9 ô, tốn 4GB RAM. Quy tắc: dùng Counting sort khi k = O(n). Nếu k lớn, chuyển sang Radix sort (chia key thành các chữ số nhỏ hơn).

Bẫy 2: Quick sort với input sorted hoặc nearly-sorted. Quick sort ngây thơ (pivot là phần tử đầu) trên mảng đã sắp xếp cho worst case O(n²): mỗi lần partition chia thành 0 và n-1 phần tử. Tình huống này gặp nhiều khi sort file log đã có timestamp tăng dần. Cách sửa: pivot ngẫu nhiên hoặc median-of-three. Arrays.sort(int[]) của Java dùng Dual-Pivot Quicksort kèm lấy mẫu pivot và nhánh heap sort khi đệ quy suy biến.

Bẫy 3: Nhầm stable sort với in-place sort. Heap sort in-place nhưng không stable. Merge sort stable nhưng không in-place (cần buffer O(n)). Quick sort không stable (swap có thể đảo thứ tự các phần tử bằng nhau) và cũng không hẳn in-place (đệ quy tốn O(log n) stack). Khi sort object theo nhiều key lần lượt (sort theo ngày, rồi sort theo tên), cần stable sort để giữ thứ tự ngày trong cùng nhóm tên.

Bẫy 4: External merge sort không kiểm soát số file descriptor. Nếu k-way merge mở quá nhiều chunk file cùng lúc, giới hạn file descriptor của hệ điều hành (mặc định 1024 trên Linux) sẽ báo lỗi. Cách sửa: giới hạn số chunk mỗi lần merge (ví dụ k=256), rồi merge nhiều vòng cho đến khi còn 1 file. Đây là k-way merge nhiều tầng, độ phức tạp vẫn O(n log n).

Bẫy 5: Dùng Java Arrays.sort(Integer[]) cho khối lượng dữ liệu toàn số nguyên thuỷ. Arrays.sort(Integer[]) dùng TimSort, stable nhưng mỗi phần tử là một object nên tốn bộ nhớ và truy cập rải rác hơn. Arrays.sort(int[]) dùng Dual-Pivot Quicksort trực tiếp trên kiểu nguyên thuỷ, thường nhanh hơn rõ rệt khi n lớn. Nếu thật sự cần stable sort trên giá trị nguyên thuỷ, bạn phải boxing hoặc tự cài Merge sort.

Tự kiểm tra

Bạn đã đạt module này nếu trả lời được:

• So sánh được ít nhất 5 thuật toán sắp xếp theo time / space / stability, và giải thích khi nào chọn Quick sort thay Merge sort, khi nào Counting sort vượt cả hai.
  • Nếu chưa: đọc lại bài 01 (sort landscape, bảng so sánh) và bài 06 (counting/radix/bucket).
• Giải thích được cận dưới Ω(n log n) của comparison sort bằng cây quyết định, và chỉ ra điều kiện để non-comparison sort vượt qua giới hạn đó.
  • Nếu chưa: đọc lại bài 01 (mục 3, cận dưới bằng cây quyết định).
• Cài được merge sort và quick sort bằng pseudocode, ghi rõ best / average / worst case và giải thích nguyên nhân của worst case.
  • Nếu chưa: đọc lại bài 03 (merge sort) và bài 04 (quick sort, mục partition + worst case).
• Thiết kế được external merge sort cho file vượt RAM: mô tả hai pha (tạo sorted run rồi k-way merge) và giải thích vì sao TimSort tốt hơn Merge sort thuần trên dữ liệu thực tế.
  • Nếu chưa: làm lại bài 08 (mini-challenge) và đọc bài 09 (TimSort run detection + galloping).

Bài tiếp theo

Bạn đã có nền vững về sắp xếp, từ lý thuyết Ω(n log n) tới case study production. Module tiếp theo, Đường đi & quan hệ, mở ra một chiều khác: dữ liệu không còn là dãy tuyến tính mà là mạng lưới quan hệ. Bạn sẽ gặp BFS/DFS, Dijkstra, Bellman-Ford, Kruskal/Prim và topological sort, những thuật toán nằm trong routing, build system và recommendation engine. Dijkstra dùng lại đúng PriorityQueue và heap bạn vừa học.

Bài tiếp theo: Đường đi & quan hệ: tổng quan

Tài liệu mở rộng

• Sách: Introduction to Algorithms (CLRS), Chapters 6 (Heapsort), 7 (Quicksort), 8 (Sorting in Linear Time). Chapter 8.1 là bản chứng minh chặt chẽ nhất của cận dưới comparison sort.
• Sách: Algorithm Design của Kleinberg & Tardos. Chapter 5 (Divide and Conquer) phân tích công thức truy hồi của Merge sort rất rõ.
• Source code: OpenJDK TimSort.java — đọc song song với bài 09, chú ý method mergeCollapse() là chỗ cài đặt invariant của merge stack.
• Paper: Tim Peters — listsort.txt, tài liệu gốc của Tim Peters mô tả thiết kế TimSort cho Python. Dài nhưng rất dễ đọc.
• Source code: Redis t_zset.c — bản cài đặt ZSET, tìm hàm zslInsert, zslGetRank để xem trường span được dùng thế nào.
• Blog: Sorting Algorithms Visualized — hoạt hình từng bước cho mọi thuật toán trong module, tốt để kiểm tra trực giác của bạn.