CSD201 - Phần 6: Các thuật toán sắp xếp

Ứng với CLO6, buổi 41-48. Tương ứng Chương 12 của Goodrich ấn bản 6. Phần này đi qua bảy thuật toán sắp xếp, với mỗi thuật toán đều phân tích cách hoạt động từng bước trên một mảng ví dụ, số phép so sánh và số phép hoán đổi, độ phức tạp ở trường hợp tốt nhất - trung bình - xấu nhất, nhu cầu bộ nhớ phụ và tính ổn định. Nhóm cơ bản gồm sắp xếp chọn, sắp xếp chèn và sắp xếp nổi bọt, đều có độ phức tạp bình phương nhưng khác nhau về hành vi trên dữ liệu đã gần sắp xếp. Nhóm nâng cao gồm sắp xếp nhanh với cách chọn phần tử chốt và trường hợp xấu nhất, sắp xếp trộn với tư tưởng chia để trị và độ phức tạp ổn định, cùng sắp xếp vun đống dựa trên cấu trúc heap. Nhóm tuyến tính gồm sắp xếp theo thùng và sắp xếp theo cơ số, không dựa trên so sánh nên vượt được cận dưới. Khép lại bằng bảng so sánh tổng hợp và tiêu chí chọn thuật toán.