THUẬT TOÁN SẮP XẾP NÀO LÀ NHANH NHẤT?

Ngày đăng: Thứ Hai, 18/02/2019

Người viết: Tran Tien Thanh

Lời nói đầu

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), 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.

Nhìn vào bảng trên thì rõ ràng Quick Sort có độ 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 1 chút, chúng ta hãy thử đặt câu hỏi ngược lại ở đây xem sao nhé: “Nếu QuickSort là nhanh nhất thì tại sao lại còn phải đẻ ra ti tỉ các loại thuật toán sắp xếp khác làm cái lề gì nhỉ?”

Tiếp theo, chúng ta sẽ xem tốc độ sắp xếp của các thuật toán dựa theo dữ liệu đầu vào, dữ liệu ở đây có các case từ dữ liệu Random đến Nearly Sorted hay cả việc Reversed Dữ liệu

Nhìn vào thống kê phía trên, có thể thấy với mỗi kiểu dữ liệu khác nhau thì lại có 1 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 khi với những kiểu dữ liệu phức tạp hơn thì Insertion Sort lại không phải là nhanh nhất. Như vậy, từ những thống kê trên chúng ta đã dần dần hình dung ra đáp án cho câu hỏi “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ì?

=> “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ố” Và “phụ thuộc vào nhiều yếu tố” cũng là lý do mà có rất nhiều loại thuật toán sắp xếp khác nhau ra đời. Chúng ta nhìn vào 1 vài ví dụ cụ thể dưới đây để thấy những yếu tố nào sẽ ảnh hưởng việc lựa chọn thuật toán

  • Quick Sort sẽ là tốt nhất nếu …
  1. Không lo lắng về các 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. Không quan tâm đến dung lượng bộ nhớ, bộ nhớ là hoàn toàn lý tưởng và phù 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, có thể sử dụng Heap (hoặc ít nhất là Quick3) với độ phức tạp NlogN
  • Tim Sort sẽ có độ 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 1 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 lớn các 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, có sắp xếp sẵn hay không, 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 không bao giờ lừa dối chúng ta cả”. Và thực sự thì khi 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 câu hỏi thuật toán sắp xếp vô cùng đơn giản nhưng chúng ta có 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 câu hỏi cho vấn để đang được hỏi, để từ đó phân tích tìm ra câu trả lời chính xác nhất. Đôi khi 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, không có gì là hoàn hảo 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ý.

Nguồn Techtalk via Viblo

CÁC TIN TỨC, SỰ KIỆN KHÁC


5 BÀI TOÁN LẬP TRÌNH MÀ BẤT KỂ LẬP TRÌNH VIÊN NÀO CŨNG CẦN CÓ KHẢ NĂNG GIẢI QUYẾT TRONG VÒNG 1 GIỜ
5 bài toán lập trình mà bất kể lập trình viên nào cũng cần có khả năng giải quyết trong vòng 1 giờ
Thứ Hai, 18/03/2019 bởi Techtalk via Viblo

Viết 3 hàm tính tổng của các số trong 1 dãy cho trước sử dụng for-loop, while-loop, và để quy.


BÁO CÁO MỚI NHẤT VỀ THỊ TRƯỜNG IT & TÌNH HÌNH NHÂN LỰC IT VIỆT NAM
Báo cáo mới nhất về thị trường IT & tình hình nhân lực IT Việt Nam
Thứ Năm, 14/03/2019 bởi Nguồn: Báo cáo của TopDev

Thị trường lao động riêng ngành lập trình sẽ cần 350.000 nhân lực đến trước cuối năm 2021 trong khi với khả năng hiện tại chỉ có khoảng 200.000 lao động đáp ứng được nhu cầu công việc.


ARENA MULTIMEDIA: ĐÒN BẨY SÁNG TẠO CHO NGƯỜI TRẺ VIỆT
Arena Multimedia: Đòn bẩy sáng tạo cho người trẻ Việt
Thứ Năm, 14/03/2019 bởi Theo Kênh14

Sự chuyển mình của ngành Mỹ Thuật Đa Phương Tiện Việt Nam (MTĐPT), với sự đồng hành của Arena Multimedia, không chỉ góp phần mang lại doanh thu tỷ đô mà còn tạo nên một thế hệ người trẻ đủ sức góp mặt trong những dự án đẳng cấp thế giới.


CODE CHALLENGE - SÂN CHƠI LẬP TRÌNH CHO SINH VIÊN MIỀN TRUNG
Code Challenge - Sân chơi lập trình cho sinh viên Miền Trung
Thứ Tư, 13/03/2019 bởi Softech Aptech

Code Challenge 2019 là một sân chơi công nghệ mới mẻ, mang đến loạt thử thách hấp dẫn cho các bạn sinh viên chuyên ngành IT. Cuộc thi lần đầu tiên được tổ chức có quy mô hoành tráng hàng đầu Miền Trung (phạm vi thí sinh toàn miền Trung) và vòng chung kết diễn ra tại Đà Nẵng.


APTECH ĐỘT PHÁ: HỌC HAI NĂM NHẬN HAI BẰNG LẬP TRÌNH QUỐC TẾ
Aptech đột phá: Học hai năm nhận hai bằng lập trình quốc tế
Thứ Tư, 13/03/2019 bởi Theo 24h

Hàng năm, nước ta có hàng ngàn sinh viên tốt nghiệp đại học ra trường, nhưng nhiều doanh nghiệp CNTT vẫn ca thán nhân sự ngành lập trình rất “thiếu và yếu”.Nên học lập trình ở đâu để ra trường làm được việc ngay? Đột phá với chương trình rút gọn, nhận song bằng quốc tế, đào tạo chú trọng nhu cầu doanh nghiệp, Aptech chính là lời giải cho bài toán nhân lực ngành CNTT.


SỬ DỤNG TRIGGER TRONG SQL QUA VÍ DỤ CƠ BẢN.
Sử dụng trigger trong SQL qua ví dụ cơ bản.
Thứ Hai, 11/03/2019 bởi Nguồn: Phạm Anh Tuấn/Viblo

Hiểu đơn giản thì Trigger là một stored procedure không có tham số. Trigger thực thi một cách tự động khi một trong ba câu lệnh Insert, Update, Delete làm thay đổi dữ liệu trên bảng có chứa trigger. 

XEM THÊM


KẾT NỐI VỚI CHÚNG TÔI