Trong khoa học máy tính, thuật toán sắp xếp là thuật toán sắp xếp các phần tử của danh sách theo thứ tự. Các thứ tự được sử dụng thường xuyên nhất là thứ tự số và thứ tự từ điển, tăng dần hoặc giảm dần. Sắp xếp hiệu quả rất quan trọng để tối ưu hóa hiệu quả của các thuật toán khác (chẳng hạn như thuật toán tìm kiếm và hợp nhất) yêu cầu dữ liệu đầu vào phải nằm trong danh sách được sắp xếp. Sắp xếp cũng thường hữu ích để chuẩn hóa dữ liệu và để tạo đầu ra mà con người có thể đọc được
Về hình thức, đầu ra của bất kỳ thuật toán sắp xếp nào cũng phải thỏa mãn hai điều kiện
- Đầu ra theo thứ tự đơn điệu (mỗi phần tử không nhỏ hơn/lớn hơn phần tử trước đó, theo thứ tự yêu cầu)
- Đầu ra là một hoán vị (sắp xếp lại nhưng vẫn giữ lại tất cả các phần tử ban đầu) của đầu vào
Để có hiệu quả tối ưu, dữ liệu đầu vào phải được lưu trữ trong cấu trúc dữ liệu cho phép truy cập ngẫu nhiên thay vì cấu trúc chỉ cho phép truy cập tuần tự
Lịch sử và khái niệm[sửa | sửa mã nguồn]
Ngay từ khi bắt đầu có máy tính, bài toán sắp xếp đã thu hút rất nhiều nghiên cứu, có lẽ do tính phức tạp của việc giải nó một cách hiệu quả mặc dù cách phát biểu đơn giản, quen thuộc của nó. Trong số các tác giả của thuật toán sắp xếp sớm vào khoảng năm 1951 có Betty Holberton, người đã làm việc trên ENIAC và UNIVAC. Sắp xếp bong bóng được phân tích sớm nhất là vào năm 1956. Các thuật toán tối ưu tiệm cận đã được biết đến từ giữa thế kỷ 20 – các thuật toán mới vẫn đang được phát minh, với thuật toán Timsort được sử dụng rộng rãi từ năm 2002 và thuật toán sắp xếp thư viện được xuất bản lần đầu vào năm 2006
Các thuật toán sắp xếp so sánh có yêu cầu cơ bản là so sánh Ω(n log n) (một số chuỗi đầu vào sẽ yêu cầu bội số của n log n so sánh, trong đó n là số phần tử trong mảng được sắp xếp). Các thuật toán không dựa trên so sánh, chẳng hạn như sắp xếp đếm, có thể có hiệu suất tốt hơn
Các thuật toán sắp xếp phổ biến trong các lớp khoa học máy tính nhập môn, trong đó sự phong phú của các thuật toán cho vấn đề cung cấp phần giới thiệu nhẹ nhàng về nhiều khái niệm thuật toán cốt lõi, chẳng hạn như ký hiệu O lớn, thuật toán chia để trị, cấu trúc dữ liệu như đống và nhị phân.
Sắp xếp các mảng nhỏ một cách tối ưu (trong ít phép so sánh và hoán đổi nhất) hoặc nhanh (i. e. có tính đến các chi tiết cụ thể của máy) vẫn là một vấn đề nghiên cứu mở, với các giải pháp chỉ được biết đến với các mảng rất nhỏ (