Lời mở đầu Ngồi trên ghế trường Đạ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 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 công nghệ thông tin 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?”
Cùng nhau xem nào, nghe câu chữ thì thấy thằng Quick Sort là nhanh rồi, 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 trên 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? Nhưng, chúng ta hãy thử đặt câu hỏi ngược lại ở đây xem sao nhé: “Nếu QuickSort 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 gì?”
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 đó.
=> “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
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…
Một sự thật là : “Code không bao giờ lừa dối chúng ta cả”. Ở đâ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ế:
Tham khảo: Viblo
Hãy bày tỏ suy nghĩ của bạn ở dưới comment để chúng ta có những cái nhìn đa chiều nhất về vấn đề bạn đang gặp phải cũng như về lập trình.
DevPro Việt Nam - Đào tạo và phát triển IT hàng đầu Việt Nam.
13 February 2019
21 December 2018
16 November 2018
05 July 2018
16 July 2018
09 July 2018
18 February 2019
18 February 2019
23 January 2019
17 January 2019