Thuở còn ngồi trên ghế trường học đại học, khi học môn “Cấu trúc Dữ liệu & Giải thuật” hay là lúc đi phỏng vấn ở 1 công ty ABC, XYZ nào đó, mà cũng có thể đến tận lúc ngồi trà đá bàn luận với anh em đồng nghiệp chuyện nghề, chuyện nghiệp … thì chắc hẳn đã từng có lần anh em Dev chúng ta được hỏi hoặc là nghe thấy câu hỏi: “Thuật toán sắp xếp nào là nhanh nhất?” Và bài viết này của mình sẽ phần nào giúp các bạn tìm ra đáp án cho câu hỏi trên.
Câu trả lời là QuickSort, TimSort hay Insertion Sort nhỉ?
Xem nào, nghe câu chữ thì đã thấy thằng Quick Sort có vẻ là nhanh rồi (Quick là nhanh mà), và thực tế, thì Quick Sort cũng là đáp án được nhiều người lựa chọn nhất khi được hỏi câu hỏi trên. Nhưng thực tế, thì lại không phải vậy, phần lớn mọi người đã sai khi lựa chọn Quick Sort là câu trả lời của mình. Vậy đáp án là Tim Sort ư? hay Insertion Sort nhỉ Cùng nhìn vào bảng thống kê độ phức tạp trung bình của các thuật toán sắp xếp
Vậy câu trả lời đúng là gì?
Không có 1 bất kỳ thuật toán sắp xếp nào cụ thể cả, nó còn phụ thuộc vào nhiều yếu tố !
Điểm danh các thuật toán sắp xếp
24 thuật toán sắp xếp sẽ được lên đấu trường hôm nay:
- BlockMerge Sort
- BST Sort (Binary Search Tree)
- Bubble Sort
- Counting Sort
- Flash Sort
- Heap Sort
- Insertion Sort
- Interchange Sort
- Intro Sort (std::sort)
- Merge Sort (std::stable_sort)
- Merge Sort (top-down)
- Merge Sort (bottom-up)
- Noname Sort
- Super Noname Sort
- Quick Sort
- Quick Sort (3-way)
- Radix Exchange Sort
- Radix Sort 4
- Radix Sort 8
- Radix Sort 16
- Selection Sort
- Shell Sort
- Smooth Sort
- Tim Sort
Mình sẽ test tất cả 24 thuật toán này và tìm ra quán quân vô địch.
Chuẩn bị:
- Tất cả thuật toán sắp xếp (tất nhiên rồi)
- Code đếm thời gian (high resolution)
- Code random array
- CPU core i7 RAM 64 GB Windows 10 Pro Visual Studio C++
Với arguments ở trên, mình đã sinh ra mảng gồm 10 phần tử ngẫu nhiên, mỗi phần tử nằm trong đoạn [5, 11]. Dữ liệu xuất ra tập tin “10.txt”.
Tất cả thuật toán sẽ trải qua 5 test cases, mỗi test case bao gồm 3 trường hợp: mảng tăng dần, mảng giảm dần và mảng ngẫu nhiên. Mỗi thuật toán đều sắp xếp tăng dần. Ngoài ra còn có 1 test case về resource.
Kết quả test là thời gian chạy của mỗi thuật toán (tính bằng nano giây). Chỉ đo thời gian xử lý, cụ thể hơn, thời gian được tính kể từ lúc sau khi input, xử lý và dừng khi xử lý xong.
Ghi chú: 1 giây = 1 000 000 000 nano-giây.
Bắt đầu vòng đấu
a. Test case 1 – 10 000 phần tử
Bình thường mảng có khoảng vài chục, vài trăm phần tử là đã phê rồi. Đằng này đến 10 nghìn phần tử, có vẻ lớn ghê. Thật ra không phải như vậy, 10.000 vẫn còn quá nhỏ bé.
Với n = 10 000, mỗi phần tử nằm trong đoạn [0, 9999] thì đây là kết quả:
Theo mặc định, dữ liệu ngẫu nhiên sẽ chiếm hầu hết trường hợp, vì vậy mình ưu tiên đánh giá theo input ngẫu nhiên.
Chót bảng không ai khác ngoài 3 người anh em nổi tiếng Interchange Sort, Bubble Sort và Selection Sort. Nổi tiếng là vì nó quá thông dụng, dễ cài đặt. Tuy nhiên cái gì cũng có cái giá của nó. Nếu code cài đặt ngắn, thuật toán suy nghĩ đơn giản thì có lẽ chúng thường chỉ giải quyết các vấn đề đơn giản.
Nhưng, tất cả chỉ mới bắt đầu. 138 368 700 nano-giây ≈ 0.14 giây mà thôi. Chưa đến 1 giây nên cảm giác của chúng ta không có gì khác biệt.
b. Test case 2 – 100 000 phần tử
Trong lần test này, n = 100 000, mỗi phần tử nằm trong đoạn [0, 99999].
Vâng, chúng ta lại xác định được rõ top 5 chạy chậm nhất, nhìn thấy rõ luôn. Với top 17 chạy nhanh thì sự khác biệt không đáng kể. Trong top 2 có Counting Sort và Heap Sort chạy rất nhanh.
Thuật toán 3-way Quick Sort khi sort thì bị stack over-flow (do code cần đệ quy khá nhiều) -> thua
Chúng ta cũng chia tay luôn 5 chiến sĩ chót bảng vì chạy quá chậm: Insertion Sort, Shell Sort, Selection Sort, Bubble Sort, Interchange Sort. -> thua
c. Test case 3 – 5 000 000 phần tử
Vâng, 5 triệu phần tử, nhưng trong thực tế con số 5 triệu vẫn còn khá nhỏ.
Giá trị mỗi phần tử sẽ nằm trong đoạn [0, 4 999 999]
Top 3 chạy nhanh ngang nhau: 2 anh em nhà Radix Sort và Super Noname Sort, Counting Sort bám sát đằng sau top4.
Tất nhiên, ở đây ta ưu tiên xét theo input ngẫu nhiên, với input tăng dần và giảm dần thì chỉ xem thôi.
Nhìn vào đồ thị trên, ta rút ra một số nhận xét:
- Một số thuật toán chạy cực nhanh khi dữ liệu đã được sắp xếp sẵn. Ví dụ: Tim Sort, Counting Sort.
- Với input giảm dần, một số thuật toán tỏ ra rất chậm chạp, ví dụ như Merge Sort, BlockMerge Sort, Smooth Sort.
- Một số thuật toán khi chạy với input ngẫu nhiên thì lại nhanh. Ví dụ như Radix Sort, Super Noname Sort.
d. Test case 4 – 20 000 000 phần tử
Vâng, 20 triệu là một con số không nhỏ.
Top chạy nhanh nhất: vẫn là anh em nhà Radix Sort, Super Noname Sort, Counting Sort.
Top chạy khá nhanh: Quick Sort, Merge Sort, Intro Sort.
Thuật toán chạy nhanh nhất khi dữ liệu đã được sắp xếp đó chính là Tim Sort còn BlockMerge Sort và Smooth Sort khi input đã sắp xếp tăng dần thì thời gian rất thấp nhưng khi input sắp xếp giảm dần thì …
Chúng ta cùng nhau nói lời chia tay với 4 thí sinh chót bảng bao gồm Merge Sort (top-down), Noname Sort, Heap Sort và Smooth Sort -> thua
e. Test case 5 – 50 000 000 phần tử
Vâng, 50 triệu phần tử, một con số không hề nhỏ, đủ để gây khó khăn bất cứ thuật toán sort nào. Đây là bộ test quyết định thuật toán nào sẽ thật sự dành chiến thắng.
Với 50 triệu phần tử, file input có sơ sơ nửa GigaBytes
Và kết quả là ….
- Quán quân: anh em nhà Radix Sort.
- Á quân: Super Noname Sort.
- Quý quân: Counting Sort.
- Bét bảng: Flash Sort.
f. Test case 6 – 100 000 000 phần tử
Ta sẽ xem xét “độ nặng” của các thuật toán.
Thuật toán Merge Sort top-down chiếm bộ nhớ nhiều khủng khiếp khi ngốn đến 12500 MB ~ 12.5 GB RAM, ôi trời!
Tiếp đến là Noname Sort. Thuật toán này được bảo đảm chạy với tốc độ O(n log log n) cho trường hợp xấu nhất. Nó sử dụng danh sách liên kết nên việc ăn nhiều RAM cũng không phải là điều khó hiểu 3000 MB ~ 3 GB.
Cuối cùng là BST Sort, dễ dàng nhận thấy vì xử lý trên cây nhị phân, nên cần rất nhiều bộ nhớ cho các node 2300 MB ~ 2.3 GB.
Nếu xét riêng về CPU thì không có sự khác nhau nhiều.
Ngoài lề
Tổng hợp thông tin các thuật toán sort
Nguồn: Wikipedia
Lời khuyên cho những bạn mới học lập trình
Bạn không cần phải học hết tất cả các thuật toán sort. Bạn chỉ cần hiểu nguyên lý của nó, học vài thuật toán thông dụng như Interchagne Sort, Bubble Sort, Selection Sort. Sau đó nâng cao hơn thì bạn có thể học Quick Sort, Merge Sort.
