Thuật toán sắp xếp nào là nhanh nhất?

Lời nói đầu

Thuở còn ngồi trên ghế trường học đại học, lúc học môn "Cấu trúc Dữ liệu & Giải thuật" hay là lúc đi phỏng vấn ở một tổ chức ABC, XYZ nào đó, mà cũng mang thể tới 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 mang lần anh em Dev chúng ta được hỏi hoặc là nghe thấy nghi vấn: "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 những bạn tìm ra đáp án cho nghi vấn 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 mang vẻ là nhanh rồi (Quick là nhanh mà :v), và thực tế, thì Quick Sort cũng là đáp án được nhiều người lựa chọn nhất lúc được hỏi nghi vấn trên. Nhưng thực tế, thì lại ko phải vậy, phần to mọi người đã sai lúc 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 những thuật toán sắp xếp Quan sát bảng trên thì rõ ràng Quick Sort mang độ phức tạp trung bình là O(n log(n)), ơ chẳng phải dựa vào kết quả này thì Quick Sort là nhanh nhất còn gì nữa? Chậm lại một chút, chúng ta hãy thử đặt nghi vấn trái lại ở đây xem sao nhé: "Nếu QuickSort là nhanh nhất thì vì sao lại còn phải đẻ ra ti tỉ những loại thuật toán sắp xếp khác làm chiếc lề gì nhỉ?"

Tiếp theo, chúng ta sẽ xem tốc độ sắp xếp của những thuật toán dựa theo dữ liệu đầu vào, dữ liệu ở đây mang những case từ dữ liệu Random tới Nearly Sorted hay cả việc Reversed Dữ liệu Quan sát thống kê phía trên, mang thể thấy với mỗi kiểu dữ liệu khác nhau thì lại mang một kiểu sắp xếp chiếm ưu thế riêng, ví dụ với dữ liệu Nearly Sorted thì Insertion Sort là nhanh nhất nhưng lúc với những kiểu dữ liệu phức tạp hơn thì Insertion Sort lại ko phải là nhanh nhất. Tương tự, từ những thống kê trên chúng ta đã dần dần hình dung ra đáp án cho nghi vấn "Thuật toán sắp xếp nào là nhanh nhất" rồi nhỉ

Vậy câu trả lời đúng là gì?

  • Quick Sort sẽ là tốt nhất nếu ...
  1. Ko lo lắng về những case đầu vào kể cả trường hợp xấu nhất (trật tự nói chung là ngẫu nhiên)
  2. Ko quan tâm tới dung lượng bộ nhớ, bộ nhớ là hoàn toàn lý tưởng và thích hợp ở đây
  • Nếu dữ liệu đã được sắp xếp sẵn, thì nên chọn Insertion Sort hoặc Shell Sort sẽ tốt hơn.

  • Nếu chúng ta thực sự phải loại bỏ case xấu nhất, mang thể sử dụng Heap (hoặc ít nhất là Quick3) với độ phức tạp NlogN

  • Tim Sort sẽ mang độ phức tạp thấp hơn Quick Sort ở cả Best Case lẫn Worse Case, Tim Sort là sự kết hợp của Merge Sort và Insertion Sort. Python sử dụng thuật toán sắp xếp này là mặc định của họ

  • Trong trường hợp, dữ liệu rất ít phần tử (10-20 phần tử), lựa chọn Selection Sort sẽ nhanh hơn Quick Sort

    Tóm lại một lần nữa , về lý thuyết thì Quick Sort thật sự là thuật toán sắp xếp nhanh nhất trong phần to những trường hợp. Tuy nhiên, trên thực tế, việc lựa chọn thuật toán sắp xếp dựa vào nhiều yếu tố như dữ liệu đầu vào số lượng như thế nào, mang sắp xếp sẵn hay ko, dung lượng bộ nhớ ra sao, tốc độ xử lý CPU...

Thuật toán và bài học cuộc sống

Mình vẫn thường hay nói đùa rằng: "Code ko bao giờ lừa dối chúng ta cả". Và thực sự thì lúc Code mình cũng chiêm nghiệm ra nhiều bài học cuộc sống cho chính mình luôn. Ở đây, từ một nghi vấn thuật toán sắp xếp vô cùng thuần tuý nhưng chúng ta mang thể rút ra được rất nhiều bài học thực tế:

  • Hãy học cách đặt lại nghi vấn cho vấn để đang được hỏi, để từ đó phân tích tìm ra câu trả lời xác thực nhất. Thỉnh thoảng làm dự án thực tế, khách hàng sẽ đưa ra những yêu cầu mơ hồ, thay vì cắp đầu vào tìm giải pháp, hay code thì chúng ta hãy hỏi rõ khách hàng, làm rõ vấn đề đó trước đã
  • Trong cuộc sống, ko mang gì là tuyệt vời cả hãy nhìn đặt vấn đề gặp phải dưới nhiều góc nhìn khác nhau, để cân nhắc và lựa chọn giải pháp cho hợp lý

Tài liệu tham khảo

https://www.quora.com/What-is-the-fastest-sorting-algorithm https://stackoverflow.com/questions/7770230/comparison-between-timsort-and-quicksort http://javarevisited.blogspot.com/2017/02/difference-between-comparison-quicksort-and-non-comparison-counting-sort-algorithms.html

Leave a Comment

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *