Giải Mã Lời Gọi Hàm std::sort() Trong C++
Chắc hẳn khi lập trình với C++ bạn ít nhất 1 lần đã nghe đến thư viện chuẩn STL, phải nói rằng STL cung cấp cho dân coder chúng ta những công cụ hỗ trợ mạnh mẽ (các thuật toán và cấu trúc dữ liệu được định nghĩa sẵn) mà 1 trong số đó là sắp xếp.
Vậy bạn đã bao giờ đặt câu hỏi thuật toán ẩn sau việc sắp xếp được sử dụng trong thư viện chuẩn STL là gì chưa? Trong bài viết này hãy cũng mình trả lời câu hỏi đó nhé!
1. Ý tưởng thuật toán
Trước hết, chắc hẳn chúng ta đều biết trong trường hợp xấu nhất(worst case), Quick Sort có độ phức tạp là O(n2)(trường hợp này xảy ra khi dãy đã được sắp xếp và khi sắp xếp chúng ta chọn pivot là phần tử đầu tiên hay cuối cùng của dãy).
(link ảnh: Lecture 28, November 25, 1996 (dartmouth.edu))
Để khắc phục vấn đề trên, 1 giải pháp được đưa ra là phương pháp median-of-3. Phương pháp này nghĩa là trong quá trình chọn pivot, chúng ta sẽ lấy phần tử đầu tiên, phần tử ở giữa và phần tử cuối cùng của dãy sau đó chọn ra trung vị của 3 phần tử này để làm pivot.
Tuy nhiên, vẫn tồn tại 1 số dãy mà phương pháp median-of-3 cho độ phức tạp O(n2), những dãy như vậy được gọi là “median-of-3 killer“.
.png)
1 ví dụ về “median-of-3 killer”
Intro Sort được tác giả David R. Musser lần đầu giới thiệu vào năm 1997 để giải quyết vấn đề trên. Và theo như thử nghiệm của tác giả trong trường hợp sắp xếp 1 dãy “median-of-3 killer” có kích thước 100,000 phần tử, Intro Sort cho tốc độ nhanh gấp 200 lần so với Quick Sort có sử dụng median-of-3.
Như mình đã từng đề cập ở bài viết Đâu Mới Là Thuật Toán Sắp Xếp Tốt Nhất? (codelearn.io), mỗi thuật toán sắp xếp sẽ thích hợp với 1 số loại dữ liệu đầu vào. Do đó, Intro Sort lợi dụng tư tưởng trên để tối ưu thuật toán, tùy vào dữ liệu đầu vào mà sẽ dùng thuật toán thích hợp để sắp xếp, mà cụ thể ở đây là 3 thuật toán(Insertion Sort, Heap Sort và Quick Sort).
2. Triển khai thuật toán
Lưu đồ của thuật toán Intro Sort có thể biểu diễn như sau:
.png)
Trước hết như chúng ta đã biết, Insertion Sort sẽ cho tốc độ rẩt nhanh với mảng có kích thước nhỏ, do đó khi số lượng phần tử trong mảng nhỏ hơn hoặc bằng 16, Insertion Sort là thuật toán được lựa chọn để sắp xếp mảng.
Tại sao lại là Heap Sort mà không phải Merge Sort được sử dụng để tránh worst case của Quick Sort? Câu trả lời đơn giản là vì Merge Sort sẽ tốn thêm bộ nhớ khi sắp xếp, trong khi Heap Sort thì không.
Tại sao lại là 16 và 2 * log2N? Đây là những con số mang tính gần đúng và được tính ra dựa trên các kết quả thực nghiệm.
3. Kết luận:
Trên đây là những chia sẻ của mình về thuật toán Intro Sort. Hi vọng nó giúp các bạn có một cái nhìn tổng quan về thuật toán này. Để cụ thể hơn các bạn có thể đọc thêm bài viết của chính tác giả ở đây: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.14.5196&rep=rep1&type=pdf. Chúc các bạn học tốt!
Tài liệu tham khảo:
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.14.5196&rep=rep1&type=pdf
IntroSort or Introspective sort – GeeksforGeeks
Know Your Sorting Algorithm | Set 2 (Introsort- C++’s Sorting Weapon) – GeeksforGeeks
Post Comment