Sắp xếp là 1 trong những thuật toán kinh điển và quan trọng trong lập trình. Vậy đâu là thuật toán sắp xếp tốt nhất? Hãy cùng tìm hiểu nhé
Tại sao cần phải sắp xếp?
Thử tượng tượng bạn cần tra cứu 1 từ trong từ điển, tuy nhiên cuốn từ điển đó lại không được sắp xếp theo thứ tự alphabet, các từ trong từ điển được sắp xếp theo 1 quy luật ngẫu nhiên. Khi đó, việc bạn phải làm là lật từng trang, với mỗi trang bạn lại phải cố tìm kiếm xem từ bạn cần tìm có trong trang đó hay không. Và việc này khiến bạn phải bỏ ra khá nhiều thời gian và công sức. Tuy nhiên, với 1 cuốn từ điển được sắp xếp theo thứ tự alphabet thì công việc tra cứu của bạn là khá dễ dàng.
Bạn đang xem: So sánh các thuật toán sắp xếp
(link ảnh:Dictionary.com chooses its Word of the Year for 2011 - PR Daily (google.com))
Hay thử lấy 1 ví dụ khác, nếu như bạn được cho một danh sách điểm của sinh viên toàn trường, yêu cầu đặt ra là tìm sinh viên có điểm số cao nhất, khi đó việc bạn phải làm là duyệt qua từng sinh viên và tìm ra sinh viên có điểm số cao nhất, công việc này khá dễ dàng và hoàn toàn có thể thực hiện được, thế nhưng câu chuyện không dừng lại ở đó. Bởi nếu công việc yêu cầu là lọc ra top 10 sinh viên có điểm số cao nhất để phục vụ công tác khen thưởng, với 1 danh sách chưa được sắp xếp bạn sẽ phải lần lượt tìm ra sinh viên có điểm số cao thứ nhất, thứ 2, thứ 3, ... việc này cũng làm cho bạn tốn rất nhiều thời gian và công sức, đặc biệt khi số lượng sinh viên trong danh sách càng tăng thì thời gian và công sức bạn bỏ ra cũng tỉ lệ thuận theo số lượng đó. Tuy nhiên với một danh sách sinh viên với điểm số đã được sắp xếp(giả sử sắp xếp theo thứ tự giảm dần), thì công việc của bạn đơn giản là lấy ra 10 sinh viên đầu tiên trong danh sách. Qua những ví dụ trên có thể thấy rằng, sắp xếp khiến cho những thao tác tìm kiếm hay lọc của chúng ta trở nên dễ dàng hơn rất nhiều. Chính vì vậy, sắp xếp là một trong những bài toán quan trọng trong lập trình. Trong lập trình hiện tại có không dưới 20 thuật toán phục vụ cho công việc sắp xếp.
Xem thêm: Nội Dung Phim Tân Bảng Phong Thần (Phần 1), Tân Bảng Phong Thần
| Độ phức tạp | ||||||
| STT | Thuật toán | Tốt nhất | Trung bình | Xấu nhất | Bộ nhớ | Stable |
| 1 | Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Có |
| 2 | Shaker Sort | O(n) | O(n²) | O(n²) | O(1) | Có |
| 3 | Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | Không |
| 4 | Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Có |
| 5 | Binary Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Có |
| 6 | Shell Sort | O(nlogn) | depends on gap sequence | O(n2) | O(1) | Không |
| 7 | Heap Sort | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | Không |
| 8 | Merge Sort | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | Có |
| 9 | Quick Sort | O(nlogn) | O(nlogn) | O(n²) | O(logn) | Có/Không |
| 10 | Counting Sort | O(n+k) | O(n + k) | O(n + k) | O(n + k) | Có |
| 11 | Radix Sort | O(kn) | O(nk) | O(nk) | O(n + k) | Có |
| 12 | Flash Sort | O(n) | O(n + r) | O(n²) | O(m) | Không |
Bảng thống kê một số thông số của các thuật toán(Theo Wikipedia)
Đâu mới là thuật toán sắp xếp tốt nhất?
Có lẽ đây cũng là câu hỏi của rất nhiều người khi mới học lập trình, trong bài viết nay hãy cùng mình thực hiện một thử nghiệm nhỏ với 12 thuật toán sắp xếp để tìm ra câu trả lời nhé! Thử nghiệm được tiến hành với kích thước dữ liệu đầu vào lần lượt là 3.000, 10.000, 100.000, 300.000, với các loại dữ liệu lần lượt là mảng có thứ tự ngẫu nhiên, mảng có thứ tự tăng dần, mảng có thứ tự giảm dần, mảng gần như đã có thứ tự tăng dần(sai ở 1 số vị trí), và mục đích là đưa về mảng có thứ tự tăng dần. Toàn bộ source code các bạn có thể tham khảo ở đây: HaiDuc0147/sortingAlgorithm (github.com)
Cấu hình máy thực hiện thử nghiệm:
CPU: Intel(R) Core(TM) i5 4200U CPU1.6GHz 2.3 GHz.RAM: 4 GB DDR3L 1600MHz bus.Hệ điều hành Windows 10 Pro.Compiler: Visual Studio 2015.
Bảng thống kê với dữ liệu đầu vào ngẫu nhiên
Bảng thống kê với dữ liệu đầu vào có thứ tự tăng dần
Bảng thống kê với dữ liệu đầu vào có thứ tự giảm dần
Bảng thống kê với dữ liệu đầu vào gần như có thứ tự tăng dần
Nhận xét:
Với kích thước dữ liệu đầu vào nhỏ(3000) nhìn chung tốc độ chênh lệch của các thuật toán là không rõ để nhận thấy.Với mảng đã được sắp xếp, thì Bubble Sort và Shaker Sort cho tốc độ nhanh nhất do chi phí để biết được đây là mảng có thứ tự của 2 thuật toán trên là O(n).Với mảng gần như đã được sắp xếp thì Insertion Sort và Binary Insertion Sort là những sự lựa chọn tốt nhất do số phép hoán đổi phải thực hiện ít.Selection Sort cho tốc độ khá chậm trong đa số trường hợp do độ phức tạp luôn là O(n2), do đó Selection Sort chỉ nên dùng cho các trường hợp số lượng phần tử cần sắp xếp không quá nhiều.Với mảng gần như đã được sắp xếp thì Shaker Sort cho tốc độ nhanh hơn đáng kể so với Bubble Sort, do thu hẹp được khoảng phải duyệt tiếp theo sau khi duyệt.Shell Sort, Heap Sort, Merge Sort và Quick Sort có tốc độ ổn định xuyên suốt cả 4 loại dữ liệu đầu vào.Flash Sort(được phát minh bởi Karl-Dietrich Neubert vào năm 1998) là một thuật toán cho tốc độ nhanh(thậm chí nhanh hơn cả Quick Sort) và tiêu tốn rất ít bộ nhớ, tuy nhiên cách thức xây dựng thuật toán trên khá phức tạp mà nếu có dịp mình sẽ có một bài viết riêng để nói về thuật toán này.Counting Sort và Radix Sort là những thuật toán cho tốc độ nhanh, tuy nhiên cần đánh đổi bằng cách sử dụng thêm bộ nhớ.Kết luận
Qua những thống kê và nhận xét ở trên, mình hi vọng các bạn đã có cho bản thân câu trả lời "Đâu mới là thuật toán sắp xếp tốt nhất?". Còn với mình câu trả lời đó là: Không có thuật toán sắp xếp nào là tốt nhất, nó chỉ là đơn giản là sự đánh đổi giữa không gian, thời gian và công sức bỏ ra để xây dựng thuật toán, chính vì vậy tùy thuộc vào mỗi loại dữ liệu đầu vào, không gian bộ nhớ cho phép, tốc độ cần thực thi, cấu hình máy thực hiện thuật toán mà lựa chọn thuật toán cho phù hợp. Hẹn gặp lại các bạn trong các bài viết tiếp theo!
