Mình rất ít khi viết bài về thuật toán. Lý do không phải vì mình …. dốt thuật toán mà vì bản thân mình thấy nó hơi khô khan. Vả lại, phần lớn thuật toán đã được dạy kĩ càng trong trường đại học nên mình cũng không muốn dạy lại những thứ các bạn đã biết rồi.
Tuy nhiên, hôm nay mình nổi hứng phá lệ một bữa, chúng ta sẽ cùng “phản phác quy chân”, bàn luận về một trong những thuật toán phổ biến nhất: thuật toán sắp xếp!
Chuyện thanh niên lập trình viên FA
Hãy tưởng tượng, bạn phải lòng một em gái mặt xinh ngực khủng chân dài cùng lớp lập trình (Tất nhiên điều này là hư cấu vì ngành này gái đã hiếm, gái ngực khủng chân dài lại càng hiếm).
Sau một hồi thả thính qua lại, bạn quyết định tỏ tình thì nàng bảo “Anh trả lời đúng câu hỏi thì này em sẽ đồng ý”. Vốn tự tin, bạn vỗ ngực bảo “Ok, em cứ hỏi đi!”.
Nàng nhẹ hỏi một câu hỏi đơn giản: “Thuật toán sắp xếp nào là nhanh nhất vậy anh?”. Trả lời đúng thì cuộc sống nở hoa, trả lời sai là vạn kiếp bất phục!
Ảnh minh hoạ bạn nữ cùng lớp (Gốc: Jade Raymond – Một trong các nữ lập trình viên sexy hiếm hoi ngành game)
Liệu bạn sẽ trả lời thế nào? Xem hết bài viết sẽ rõ.
Câu trả lời liệu có đơn giản?
Vô cùng tự tin vào kiến thức đã học, bạn trả lời Quick Sort! Thế là từ này bạn đã thoát kiếp FA, đi chơi có người nắm tay, tối về có chỗ chui ra chui vào.
Thế nhưng, nàng chỉ nhẹ nhàng nở nụ cười khinh bỉ, sau đó xách cặp bước ra khỏi lớp, để lại bạn đứng bơ vơ một mình vì không biết chuyện gì đã xảy ra.
Giây phút bạn mở miệng trả lời Quick Sort, bạn đã sai, sai hoàn toàn và coi như mất luôn cơ hội có gấu. Tại sao vậy, rõ ràng QuickSort có độ phức tạp trung bình là O(n log(n)), chẳng phải là nhanh nhất còn gì nữa?
Thật ra, để trả lời đúng câu hỏi này, chúng ta hãy cũng suy nghĩ về câu hỏi “Nếu QuickSort là nhanh nhất, thế *éo nào mà còn lắm thuật toán sort (bubble sort, insertion sort, …) thế?”
Phản phác quy chân, tìm về cội nguồn các thuật toán sắp xếp
Nhu cầu sắp xếp dữ liệu là rất quan trọng, do đó các thuật toán sắp xếp đã được mấy bác Computer Science nghiên cứu rất nhiều từ cách đây vài chục năm, từ thuở sơ khai của máy tính.
Lý do có nhiều thuật toán sort khác nhau là vì:
- Mỗi thuật toán sẽ sử dụng lượng bộ nhớ khác nhau.
- Có thuật toán implement đơn giản (bubble sort), có thuật toán implement phức tạp.
- Mỗi thuật toán sẽ có tốc độ xử lý nhanh hay chậm tuỳ thuộc vào dữ liệu đầu vào.
Lý do thứ 3 là điều quan trọng nhất chúng ta cần để ý.
Lấy ví dụ, với dữ liệu chỉ khoảng 10-20 phần tử, selection sort nhanh hơn Quick Sort vì không phải gọi đệ qui nhiều. (Đây cũng là lý do khi viết quicksort và merge sort, người ta dùng selection sort để sắp xếp dữ liệu với số lượng phần tử nhỏ để optimize tốc độ). Với dữ liệu đã được sắp xếp sẵn, Insertion Sort sẽ chạy nhanh hơn Quick Sort.
Ngoài ra, nếu chịu khó xem lại bảng phía trên, bạn sẽ thấy Tim Sort có độ phức tạp thấp hơn Quick Sort ở cả Best Case lẫn Worst Case. Java (JDK7) sử dụng thuật toán này để sort các mảng chưa object.
Xem kĩ hình, các bạn đã thấy với dữ liệu Nearly Sorted, Insertion Sort và Bubble Sort chạy rất nhanh, hơn hẳn các thuật toán khác
Câu trả lời đúng là gì??
Trên lý thuyết, 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. Nếu dữ liệu đầu vào là mảng có lượng phần tử lớn đến rất lớn, tần suất ngẫu nhiên thì chọn Quick Sort là hoàn toàn hợp lý.
Tuy nhiên, trên thực tế, người ta sẽ 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 bao nhiêu, đã sắp xếp sẵn hay chưa), cấu hình phần cứng, dung lượng bộ nhớ.
Do đó, nếu như trước khi trả lời, bạn chỉ cần hỏi một câu đơn giản “Dữ liệu đầu vào như thế nào, bao nhiêu phần tử, đã sắp xếp chưa…?”, hẳn nàng đã vui vẻ gật đầu đồng ý lời tỏ tình của bạn.
Bài học rút ra
Chỉ từ một câu hỏi về thuật toán sắp xếp đơn giản, chúng ta rút ra được khá nhiều bài học:
- Không nên học vẹt (nghĩ quick sort là nhanh nhất) mà phải học kĩ và nắm rõ bản chất vấn đề.
- Khi có câu hỏi, cần tìm hiểu kĩ càng trước khi trả lời. Câu hỏi “thuật toán nào nhanh nhất” cũng hay được hỏi khi đi phỏng vấn. Người phỏng vấn sẽ đánh giá bạn qua việc bạn đặt câu hỏi lại, phân tích lợi hại của các thuật toán trước khi trả lời.
- Đôi khi khách hàng cũng sẽ đưa ra một yêu cầu mơ hồ như “chị muốn sắp xếp dữ liệu tốc độ nhanh nhanh tí”. Công việc của lập trình viên chúng ta là phải hỏi rõ khách hàng, làm rõ vấn đề trước khi cắm đầu vào code tìm giải pháp.
- Trong cuộc sống, không có phương pháp nào là hoàn hảo và giải quyết được mọi vấn đề. Là lập trình viên, chúng ta phải biết nhìn sự vật từ nhiều góc nhìn, cân nhắc và lựa chọn giải pháp chứ đừng mù quáng làm theo những gì đã học (ví dụ như: cứ sắp xếp thì chọn quick sort thôi, nó nhanh nhất mà).
Tham khảo thêm:
- https://www.quora.com/What-is-the-fastest-sorting-algorithm
- https://stackoverflow.com/questions/8101546/why-is-insertion-sort-better-than-quick-sort-for-small-list-of-elements
- https://stackoverflow.com/questions/7770230/comparison-between-timsort-and-quicksort
