Sắp xếp hiệu quả: merge, shell, quick và cách chọn

Học ba thuật toán sắp xếp hiệu quả với chia để trị, so sánh kề cách quãng và chốt pivot, cùng nghệ thuật chọn thuật toán.

DễThuật toán ~90 phút

Ôn lại trước khi học

Ký hiệu Big-O và các lớp tăng trưởng Đệ quy: tư duy và cái giá

Giới thiệu

Bài này học 3 cách sắp xếp nhanh cho dữ liệu lớn. Bạn biết chọn thuật toán theo tình huống.

Kiến thức cần nhớ

Merge sort — chia rồi trộn

Chia đôi tới khi mỗi mảnh 1 phần tử.
Trộn 2 nửa đã xếp thành nửa lớn hơn.
Luôn $O(n log n)$ mọi đầu vào.
Ví dụ đời thường: chia xấp bài rồi gộp lại.
Giá phải trả là tốn bộ nhớ phụ $O(n)$ .

Shell sort — chèn nhảy cóc

So sánh các món cách nhau 1 khe hở.
Khe hở thu nhỏ dần, lượt cuối bằng 1.
Lượt đầu đưa món về gần đúng chỗ.
Ví dụ đời thường: nhảy cóc thay vì bò từng bước.
Tốt cho dữ liệu cỡ vài nghìn.
Độ phức tạp phụ thuộc dãy khe: khe Knuth cho khoảng $O(n^{1.5})$ , chưa có dãy khe nào đạt $O(n \log n)$ .

Quick sort — phân hoạch quanh chốt

Chọn 1 chốt, chia thành nhỏ hơn và lớn hơn.
Chốt đứng đúng chỗ sau mỗi lần chia.
Trung bình $O(n log n)$ , xấu $O(n^2)$ .
Ví dụ đời thường: xếp sách quanh 1 mốc chiều cao.
Tránh chốt xấu bằng chốt ngẫu nhiên.

Thuật toán	Trung bình	Bộ nhớ phụ	Khi nào dùng
Merge	$O(n log n)$	$O(n)$	Lớn, cần ổn định
Shell	Khoảng $O(n^{1.3})$ tới $O(n^{1.5})$	$O(1)$	Cỡ trung bình
Quick	$O(n log n)$	$O(log n)$	Lớn, cần nhanh

Ví dụ

Input: trộn 1,4,7 và 2,3,6. Output: 1,2,3,4,6,7.
Giải thích: mỗi bước lấy số nhỏ hơn trong 2 đầu.

💻 Bài tập

Ngôn ngữ: C++. Nộp vào day-011/. Không dùng std::sort, std::stable_sort.

Bài 1: Merge sort

Hàm	Yêu cầu
`void merge(std::vector<int> &a, int l, int m, int r, std::vector<int> &tmp)`	Trộn `a[l..m]` và `a[m+1..r]`, dùng lại buffer `tmp`
`void mergeSort(std::vector<int> &a)`	Top-down, cấp `tmp` đúng 1 lần
`void mergeSortBottomUp(std::vector<int> &a)`	Không đệ quy, độ rộng 1, 2, 4...

merge [1,4,7 | 2,3,6]   -> [1,2,3,4,6,7]
mergeSort [38,27,43,3,9,82,10] -> [3,9,10,27,38,43,82]
mảng có phần tử trùng [2,1,2,1] -> [1,1,2,2]

Bài 2: Quick sort và Shell sort

quickSort với phân hoạch Lomuto, chốt là phần tử cuối.
quickSortRandom chốt ngẫu nhiên.
quickSort3Way phân hoạch 3 phần < chốt, = chốt, > chốt.
shellSort với dãy khe Knuth 1, 4, 13, 40, ....

Test bắt buộc: mảng đã xếp $n = 10^5$ với quickSort chốt cuối phải chạy rất chậm hoặc tràn stack. Ghi lại hiện tượng. quickSortRandom phải xong trong dưới 100 ms.

Bài 3: Benchmark và hybrid (nâng cao)

Đo 5 hàm trên 4 loại dữ liệu cỡ $n = 10^6$ (ngẫu nhiên, đã xếp, xếp ngược, nhiều trùng lặp với giá trị trong [0, 10)). So với std::sort.

algo              random   sorted   reversed   few_unique   (ms)
mergeSort         ...
quickSortRandom   ...
quickSort3Way     ...
shellSort         ...
std::sort         ...

Viết thêm introSortLite: quick sort ngẫu nhiên, đoạn con dưới 16 phần tử thì chuyển sang insertion sort. So thời gian với quickSortRandom.

Build với -O2 khi benchmark. Chạy mỗi ô 3 lần, lấy trung vị. Kiểm tra kết quả bằng std::is_sorted.

✅ Tiêu chí hoàn thành

Mọi hàm pass test ngẫu nhiên so với std::sort (1000 mảng, cỡ 0 tới 200).
Ghi lại được worst case của quick sort chốt cuối.
Bảng benchmark có số thật và 4 câu nhận xét.
Giải thích được vì sao phân hoạch 3 phần thắng khi dữ liệu nhiều trùng lặp.

❓ Câu hỏi ôn tập

Merge sort gồm 2 pha nào?
Shell sort khác insertion ở đâu?
Quick sort chia theo gì?
Dữ liệu lớn cần ổn định thì chọn ai?

🌕 Bạn đã hoàn thành ngày 11. Làm hết bài tập phía trên rồi sang ngày tiếp theo.

Ngày 10

Bộ ba sắp xếp O(n²): bubble, selection, insertion

Ngày 12

Decorator: Starbuzz Coffee và chuỗi bọc