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

Thuật toán sắp xếp nào nhanh nhất?
- 09 January 2019
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?”

QuickSort, TimSort hay Insertion Sort nhỉ?

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 đó.

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 là tốt nhất nếu như …
1. Không lo lắng về các case đầu vào kể cả trường hợp xấu nhất .
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 & bài học cuộc sống

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ế:
- 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ý.
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.

Danh mục

Bài viết nổi bật

Bài viết liên quan

Đánh giá của học viên đã tốt nghiệp

Các anh chị nhiệt tình, thân thiện. Em được mở mang nhiều kiến thức

Nguyễn Hằng ly

Các chị dạy rất dễ hiểu và nhiệt tình. Các kiến thức như trong thực tế khi em đi thực tập tại RikkeiSoft. Cám ơn các anh chị nhiều ạ. Chúc Dev có nhiều học viên hơn nữa.

Vũ Thị Hà Phương

Học ở DevPro đã giúp mình có nhiều kinh nghiệm lập trình android thực tế. Tại đây mình được các thầy dạy rất chi tiết theo một lộ trình rõ ràng của dự án cụ thể nên sau này đi làm mình rất dễ bắt nhịp với công việc.

Nguyễn Trọng Duy

Qua khoá học ở DevPro thì em đã có một “ít” vốn trong tay để có thể "bò" trong lĩnh vực vạn người mê này Trong qúa trình học thì em cảm thấy trung tâm suppost rất nhiệt tình từ đồ ăn tối, event và đầu ra :p. Có chị Quyên "sinh gái" siêu nhây và siêu lầy dụ dỗ bán rẻ học viên cho các nhà tuyển dụng :3 **** Đặc biệt các thầy có rất nhiều kinh nghiệm chỉ dạy và giúp đỡ rất nhiệt tính < mấy tháng liền bám càng đi nhờ thấy :p>

PhạmTiến Đạt

Tôi sẽ không khuyên các bạn phải đến DevPro để học tập thay vì những chỗ khác nhưng tôi đã từng là một người giống các bạn. Tôi băn khoăn không biết chọn nơi đâu làm ngọn đèn chỉ lối và tôi đến với Devpro . Mọi người khá hoà đồng , các thầy cũng cực nhiệt tình nhưng cũng có vốn kiến thức rất rộng còn lại là phụ thuộc vào sự nỗ lực của các bạn nữa thôi. Cố lên nhé. #ATran

Trần Xuân Ái

em thấy mọi thứ đều ổn, thầy giáo nhiệt tình trong cách giảng dậy, dev cũng rất quan tâm học viên . Nhưng theo quan điểm của em và nhìn từ sự phát triển của các trung tâm khác , em nghĩ mỗi khóa học ở dev nên có bài tập cũng như dự án giao cho học sinh làm để tạo áp lực cho học viên code, giữa học viên và công ty cần có những buổi giao lưu nhiều hơn, và cũng nên có 1 số bạn trợ giảng giúp thầy đi fix những lỗi cơ bản cho những bạn hay sai , chứ nhiều khi 1 mình thầy mà phải chạy đến từng bàn fix lỗi cũng k xuể , Xin chúc devpro ngày càng phát triển hơn

Nguyễn Đình Thành

Thầy giáo dạy rất nhiệt tình rất dễ hiểu, các chị quản lý vui vẻ, tạo động lực học viên. Bài giảng phong phú bao gồm nhiều kiến thức nền tảng. .., giúp học viên nắm chắc kiến thức. Có điều lớp toàn nam, ko có nữ ạ

Vũ Văn Thủy

-Thầy giáo rất nhiệt tình trong công tác giảng dạy , cũng như vui tính , thầy luôn giúp đỡ bọn e rất nhiệt tình ! Tuy chỉ học với lớp 1 thời gian không quá dài nhưng e cũng cảm thấy tuyệt vời vì đã từng là học trò của thầy ! - Chị Hằng và Chị Quyên rất vui tính và nhiệt tình giúp đỡ bọn e nữa ạ - e chúc trung tâm ngày càng đông học viên hơn nữa

Phan Trung Phú

DevPro là một môi trường tốt để cho những ai chưa biết gì về lập trình theo học. Bên cạnh đó, đội ngũ giảng viên rất chất lượng, nhiệt tình chỉ bảo cả trên lớp lẫn ở nhà. Ngoài ra tôi rất thích chính sách giới thiệu việc làm cho học viên sau khi tốt nghiệp để có thể tiếp với các doanh nghiệp uy tín. Sau hơn 4 tháng học tập tại công ty, tôi đã hoàn toàn tự tin rằng mình có thể tự học hỏi và bắt đầu làm việc ở một công ty mới với vai trò Web Developer. Cảm ơn DevPro vì tất cả!!

Nguyễn Đức Huy

Học một lúc 2 trường, nhưng mình vấn chưa biết tìm đam mê từ đâu. Từ lúc gặp chị Hằng mình đã quyết chọn theo android, và bây giờ mình chưa bao giờ thấy hạnh phúc đến thế. Mình có công việc ổn định, chuẩn bị onsite ở nhật 1 năm hi hi.

Trần An Hưng

1.Thầy đẹp trai thì không phải bàn rồi!! Lại được cái nhiệt tình!! ok. 2. Công ty có nhiệt tình hỗ trợ không? Công ty có nhiệt tình hỗ trợ sinh viên, vd:tiền học phí được chia làm 3 đợt giúp đỡ những sv khó khăn,.....

Trương Quang Trường

Em thấy trung tâm dạy tốt và chất lượng ạ. Thầy và các chị đều tận tâm, nhiệt tình và hòa đồng. Đặc biệt là giải lao giữa giờ chúng em còn được ăn nhẹ, e rất thích khoản này.

Trần Thị Hồng Nhung

Tại DevPro mình còn được học code trên tool mới nhất của Android, điều đó càng khiến mình thích thú hơn và trở nên say mê từ lúc nào không biết nữa. Không khí học ở đây rất vui vẻ, ngoài giờ học mình cùng các bạn còn được giải lao ăn nhẹ và trò chuyện cùng nhau nên rất thoải mãi.

Trương Ngọc Đức

Dev chính là nơi giúp mình tìm thấy niềm yêu thích code, cũng chính là nơi đã cho mình những bước đi đầu tiên, cho mình những kiến thức nền tảng tốt nhất trên con đường theo đuổi nghề Dev.

Nguyễn Thanh Hằng

Thầy giáo vui tính, nhiệt tình trả lời và giúp đỡ các bạn khi các bạn có thắc mắc hay khi gặp khó khăn. Các anh chị vui tính, thân thiện tạo cảm giác thoải mái và vui vẻ cho các bạn khi học ở đây.

Cao Minh Lâm

Nghĩ lại hồi đấy, không có Devpro thì chắc giờ em phát rồ mất thôi! Em vốn nghĩ mình có thể tự học được, nhưng kiến thức vốn là vô tận, không có người hướng dẫn thì mình sẽ chẳng biết bắt đầu dư lào, bước tiếp là gì? Nhờ DevPro, sự tận tâm của các thầy mà em mới biết à hóa ra mọi thứ thật đơn giản.

Kim Erico

Hồi học ở DevPro, mình rất quý thầy Việt và những người bạn. Từ kiến thức học được từ trung tâm mình đã mạnh dạn đi thực tập ở một công ty lớn của Nhật Bản và đến giờ đã là nhân viên chính thức ở đây rồi. Vui hơn nữa là có bạn học cùng lớp đó giờ đang là đồng nghiệp cùng mình luôn rồi. Hihi

Nguyễn Thanh Việt