Sắp xếp & thứ tự: tổng quan module

TL;DR: Module này giúp bạn hiểu toàn diện về sắp xếp: vì sao mọi comparison sort đều bị chặn ở Ω(n log n), cách non-comparison sort (Counting/Radix/Bucket) vượt qua giới hạn đó, và vì sao production hội tụ về TimSort cho dữ liệu trong RAM và skip list cho tập có thứ tự. Bạn sẽ tự cài được merge sort, quick sort, heap sort, phân tích các đánh đổi, thiết kế external merge sort cho file vượt RAM, và đọc được source OpenJDK TimSort cùng Redis ZSET.

Vì sao module này tồn tại

Sắp xếp là bài toán nền tảng nhất của khoa học máy tính, xuất hiện ở mọi tầng từ scheduler của hệ điều hành đến database index đến bảng trên giao diện. Nhưng "gọi hàm sort có sẵn" chưa đủ nếu bạn cần debug tốc độ, chọn thuật toán đúng cho dữ liệu cụ thể, hoặc thiết kế hệ thống xử lý dữ liệu lớn hơn RAM.

Module này trả lời ba nhóm câu hỏi mà lập trình viên hay gặp:

• Tại sao Java dùng hai thuật toán khác nhau cho int[] và Integer[]? Câu trả lời liên quan đến stability, cách tận dụng cache, và đánh đổi giữa sort kiểu nguyên thuỷ với sort object.
• Khi nào dùng Counting sort thay vì Quick sort? Câu trả lời nằm ở lý thuyết cận dưới Ω(n log n): hiểu nó thì bạn biết khi nào non-comparison sort dùng được.
• Sắp xếp file 10GB trên máy có 1GB RAM? Dùng External merge sort, một thiết kế có cấu trúc chứ không phải "đọc từng dòng".

Sau module này bạn sẽ

• Compare các thuật toán sắp xếp theo time / space / stability và chọn đúng theo dữ liệu
• Explain cận dưới Ω(n log n) của comparison sort và khi nào non-comparison sort vượt qua được
• Implement merge sort, quick sort, heap sort và phân tích best / average / worst case
• Design cách sắp xếp dữ liệu vượt RAM (external merge sort) và hiểu adaptive sort (TimSort)

Bản đồ module

Lộ trình module

Thứ tự bài theo nguyên tắc "nhìn bản đồ chung trước, học cơ chế sau":

Bài 01 — Sort landscape mở đầu bằng bản đồ tổng thể: comparison vs non-comparison sort, 5 thuộc tính phân loại (stable, in-place, adaptive, online, comparison-based), và vì sao cận dưới Θ(n log n) không thể vượt qua với comparison sort. Đọc bài này trước để các bài sau có chỗ đặt vào.

Bài 02 — Quadratic sorts đào sâu Insertion sort, Selection sort, Bubble sort: ba thuật toán O(n²) tưởng chỉ để dạy học, nhưng Insertion sort thực ra là viên gạch của TimSort và chạy hiệu quả trên dữ liệu gần như đã sắp xếp.

Bài 03 — Merge sort là thuật toán đầu tiên đạt O(n log n) được đảm bảo: chia để trị, merge stable, phân tích công thức truy hồi T(n) = 2T(n/2) + O(n), k-way merge và cách làm external sort. Đây là nền của bước merge trong TimSort.

Bài 04 — Quick sort là thuật toán nhanh nhất trong thực tế với O(n log n) trung bình và hằng số thấp: hai cách partition (Lomuto vs Hoare), cách chọn pivot, worst case O(n²) khi pivot tệ và cách tránh (pivot ngẫu nhiên, median-of-three), và vì sao Quick sort thực tế nhanh hơn Merge sort dù cùng Big-O.

Bài 05 — Heap & Heapsort gộp hai chủ đề: cấu trúc dữ liệu heap (binary heap, heapify, priority queue) và Heapsort dùng heap để sort in-place O(n log n) được đảm bảo, không cần bộ nhớ phụ như Merge sort, không có worst case như Quick sort.

Bài 06 — Counting, Radix, Bucket sort vượt qua giới hạn Ω(n log n): ba thuật toán không so sánh trực tiếp các phần tử, đạt O(n+k) hay O(n×d) khi key có khoảng giá trị hữu hạn. Bài giúp bạn biết khi nào đây là lựa chọn đúng và khi nào không.

Bài 07 — Skip list là cấu trúc dữ liệu dựa trên xác suất cho tập có thứ tự: tìm kiếm O(log n) trung bình, không cần phép xoay như BST, và dễ cài hơn BST cân bằng. Đây là nền cho bài case study Redis ZSET.

Bài 08 — Mini-challenge: External merge sort là bài thực hành thiết kế: sort file 10GB trên máy 1GB RAM. Không có "đáp án làm sẵn", bạn phải dùng merge sort và giới hạn bộ nhớ để tự thiết kế giải pháp.

Bài 09 — Case study: TimSort + Redis ZSET là đỉnh của module: đọc source OpenJDK TimSort (nhận ra run, galloping merge, invariant của merge stack) và Redis ZSET (cấu trúc kép skip list cộng dict, trường span cho ZRANK O(log n)). Bạn sẽ hiểu vì sao hai lựa chọn này thắng mọi phương án khác trong production.

Bài 10 — Tổng kết gom cheat sheet, glossary, các bẫy và phần tự đánh giá của toàn module.

Yêu cầu trước khi bắt đầu

• Đã học module Tìm kiếm nhanh, nhất là Binary search và BST. Module này mở rộng sang heap và skip list.
• Biết ký hiệu Big-O cơ bản (O, Ω, Θ), có trong bài Big-O từ bản chất.
• Đã quen vòng lặp lồng nhau (lặp lồng nhau), hàm tự gọi lại chính nó (hàm) và cách theo dõi từng bước bằng bảng trace. Bài về Merge sort, Quick sort và Heapsort dựa nhiều vào đệ quy và trace tay.
• Pseudocode của track thuật toán: từ khoá điều khiển bằng tiếng Anh (if, while, for), identifier bằng tiếng Anh, chú thích bằng tiếng Việt có dấu.

Time budget

Cách học module này hiệu quả

• Bắt đầu từ bài 01 — Sort landscape. Đừng nhảy thẳng vào Quick sort. Bức tranh tổng thể quyết định bạn đặt các bài chi tiết vào đâu.
• Tự cài trước khi đọc pseudocode. Đặc biệt với Merge sort và Quick sort: viết pseudocode từ ý tưởng "chia để trị", rồi đối chiếu với bài.
• Nhớ lý do, không chỉ độ phức tạp. Vì sao Quick sort thực tế nhanh hơn Merge sort dù cùng O(n log n)? Vì sao Heap sort ít dùng dù worst case O(n log n) được đảm bảo? Những câu hỏi này quan trọng hơn việc thuộc bảng độ phức tạp.
• Bài 08 là bài thực hành, đừng bỏ qua. External merge sort là cách làm thực tế trong pipeline xử lý dữ liệu lớn. Hãy tự thiết kế trước khi đọc lời giải.
• Bài 09 nên đọc song song với source code. Mở java.util.TimSort.java trên GitHub trong lúc đọc; thấy code thật giúp bạn neo lý thuyết vào thực tế.

Bài tiếp theo: Sort landscape