Tiểu Luận Chương trình quản lý các giải thuật sắp xếp

Một trong những vấn đề nền tảng của khoa học máy tính là sắp xếp một tập các phần tử cho trước theo thứ tự nào đó. Có rất nhiều các giải pháp cho vấn đề này, được biết đến như là các thuật toán sắp xếp (sorting algorithms). Bên cạnh các thuật toán sắp xếp đơn giản và rất rỏ ràng, như là sắp xếp nổi bọt (bubble sort). Một số khác, như phương pháp sắp xếp nhanh (quick sort) thì lại rất phức tạp nhưng đổi lại có kết quả thực thi nhanh hơn một cách đáng kể.
Những thuật toán sắp xếp quen thuộc này có thể được chia thành hai nhóm dựa theo độ phức tạp của chúng. Độ phức tạp của thuật toán (Algorithmic complexity) là một chủ đề khá rắc rối đòi hỏi sự tưởng tượng mà sẽ tốn nhiều thời gian để giải thích, nhưng ở đây có thể hiểu thông qua mối tương quan trực tiếp giữa độ phức tạp của thuật toán và hiệu quả của nó. Độ phức tạp của thuật toán thường được kí hiệu bởi một hàm O, trong đó O biểu diễn độ phức tạp của thuật toán đi kèm với một giá trị n biểu diễn kích thước của số lần chạy tối đa mà thuật toán đó dựa vào để xử lý trên dữ liệu.
Ví dụ, O(n) có nghĩa là thuật toán có độ phức tạp tuyến tính. Cụ thể hơn , nó sẽ mất thời gian gấp 10 lần cho việc xử lý trên tập dữ liệu có 100 phần tử so với tập chỉ có 10 phần tử (10 * 10 = 100). Nếu độ phức tạp là O(n2) (quadratic complexity), thì nó sẽ phải tiêu tốn thời gian gấp 100 lần để xử lý trên tập 100 phần tử so với tập dữ liệu chỉ gồm 10 phần tử.
Hai nhóm thuật toán sắp xếp được phân như sau: nhóm thứ nhất có độ phức tạp là O(n2) bao gồm bubble, insertion, selection; Nhóm thứ hai có độ phức tạp là O(n log n) gồm heap,và quick sorts.
Bên cạnh độ phức tạp của thuật toán, tốc độ của các thuật toán sắp xếp có thể được so sánh dựa vào kinh nghiệm có được từ việc thử trên các tập dữ liệu. Vì tốc độ sắp xếp có thể thay đổi rất nhiều tùy theo đặc điểm của dữ liệu, nên để các kết quả thống kê chính xác dựa trên kinh nghiệm đòi hỏi việc chạy các thuật toán nhiều lần trên các dữ liệu khác nhau và tính trung bình. Thông thường tập dữ liệu kiểm tra được tạo ngẫu nhiên.