Qua phần 1 và phần 2 của loạt bài Thuật toán sắp xếp nhiều bạn sẽ đặt câu hỏi thuật toán sắp xếp nào là tốt nhất trong các thuật toán đã nêu? Hãy cùng tìm hiểu trong bài dưới đây

Câu trả lời là Quick sort, Merge sort hay Selection sort?

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 khoan đã, nếu Quick Sort là nhanh nhất thì tại sao lại còn sinh ra rất nhiều thuật toán sắp xếp khác, chúng ta hãy 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.

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ì?

Thực ra không có thuật toán sắp xếp nào là tốt nhất cả, độ nhanh hay chậm của các thuật toán sắp xếp phụ thuộc vào rất nhiều yếu tố, trong đó yếu tố dữ liệu đầu vào chiếm một phần khá quan trọng.

Ví dụ, Quick Sort sẽ tốt nhất nếu:

  • 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)
  • 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

Còn nếu dữ liệu đã được sắp xếp sẵn, thì nên chọn Insertion Sort sẽ tốt hơn.

Chương trình minh họa

Ở đây, mình có viết một chương trình minh họa thời gian thực hiện của các thuật toán sắp xếp để các bạn dễ hình dung.

Ví dụ, khi để mảng input ít phần tử, chúng ta sẽ khó thấy sự khác biệt giữa các thuật toán

Nhưng khi để input đầu vào lớn và nhiều case đầu vào hơn, chúng ta sẽ thấy được ưu và nhược điểm của từng thuật toán.

Link project:

https://github.com/qwrite/Sorts