MỤC LỤC

MỞ ĐẦU ………………………………………………………………………………………………………………….. 1
Lịch sử phát triển………………………………………………………………………………………………………. 1
Mục đích, đối tƣợng, phạm vi nghiên cứu …………………………………………………………………. 3
Bố cục của luận văn ………………………………………………………………………………………………….. 4
Phương pháp nghiên cứu …………………………………………………………………………………………… 5
CHƯƠNG 1 TỔNG QUAN VỀ BÀI TOÁN SẮP XẾP …………………………………………….. 6
1.1 BÀI TOÁN SẮP XẾP …………………………………………………………………………………………. 6
1.1.1 Giới thiệu về bài toán sắp xếp…………………………………………………………………………… 6
1.1.2 Tầm quan trọng của bài toán sắp xếp………………………………………………………………… 6
1.1.3 Yêu cầu của bài toán sắp xếp ……………………………………………………………………………. 6
1.1.4 Các giải thuật sắp xếp hiện nay ………………………………………………………………………… 7
1.2 ỨNG DỤNG CỦA BÀI TOÁN SẮP XẾP ………………………………………………………….. 8
CHƯƠNG 2 GIẢI THUẬT QUICKSORT VÀ CÁC VẤN ĐỀ LIÊN QUAN ………….. 9
2.1. BÀI TOÁN SẮP XẾP VÀ MỘT SỐ KHÁI NIỆM …………………………………………….. 9
2.1.1 Một số khái niệm trong bài toán sắp xếp………………………………………………………….. 9
2.1.2 Phân tích giải thuật sắp xếp ……………………………………………………………………………..10
2.1.3.Sự tăng trƣởng của các hàm và độ phức tạp của giải thuật ……………………………….12
2.2. MỘT SỐ GIẢI THUẬT THÔNG DỤNG………………………………………………………….22
2.2.1 Giải thuật Mergsort …………………………………………………………………………………………22
2.2.2 Giải thuật Heapsort…………………………………………………………………………………………26
2.3 GIẢI THUẬT SẮP XẾP QUICKSORT……………………………………………………………..34
2.3.1 Giới thiệu. ……………………………………………………………………………………………………….34
2.3.2 Phân tích giải thuật Quicksort. …………………………………………………………………………34
2.3.3 Giải thuật Quicksort ………………………………………………………………………………………..35
2.3.4 Mô phỏng phân hoạch danh sách …………………………………………………………………….35
2.3.5 Độ phức tạp của giải thuật……………………………………………………………………………….36
2.3.6 Ƣu điểm, nhƣợc điểm………………………………………………………………………………………41
2.3.7 Ví dụ minh họa………………………………………………………………………………………………..42
2.3.8. Các cách chọn chốt (pivot) ……………………………………………………………………………..42
2.3.9 So sánh giải thuật Quicksort và Mergesort ……………………………………………………..43
2.3.10 So sánh Heapsort và Quicksort ………………………………………………………………………44
2.4 MỘT SỐ TRƢỜNG HỢP ĐẶC BIỆT CỦA GIẢI THUẬT QUICKSORT 46
2.4.1 Giải thuật Quicksort Dijkstra3 way………………………………………………………………….46
2.4.2.Giải thuật Quicksort Bentley-McIlroy 3 way …………………………………………………..52
2.4.3 Giải thuậtQuicksort Dual Patition – pivot ( 2 chốt ) ………………………………………….57
CHƯƠNG 3 ỨNG DỤNG THỰC NGHIỆM SẮP XẾP ………………………………………….64
3.1 LỰA CHỌN NGÔN NGỮ …………………………………………………………………………………64
3.2 GIAO DIỆN CHÍNH ………………………………………………………………………………………….65
3.2.1 Giao diện xử lý các giải thuật sắp xếp ……………………………………………………………..65
3.2.2 Giao diện so sánh giữa các giải thuật ……………………………………………………………….66
3.2.3 Kết quả thực nghiệm ……………………………………………………………………………………….66
KẾT LUẬN ……………………………………………………………………………………………………………..71
PHỤ LỤC ………………………………………………………………………………………………………………..73
CHƯƠNG TRÌNH MÔ PHỎNG TRONG LUẬN VĂN…………………………………………..73