Đang chuẩn bị liên kết để tải về tài liệu:
Giáo trình giải thuật của Nguyễn Văn Linh part 4

CHƯƠNG 2: SẮP XẾP TỔNG QUAN Mục tiêu Chương này sẽ trình bày một số phương pháp sắp xếp. Với mỗi phương pháp cần nắm vững các phần sau: Giải thuật sắp xếp. Minh họa việc sắp xếp theo giải thuật. Chương trình sắp xếp. Đánh giá giải thuật. | Giải thuật Sắp xếp CHƯƠNG 2 SẮP XẾP 2.1 TỔNG QUAN 2.1.1 Mục tiêu Chương này sẽ trình bày một số phương pháp sắp xếp. Với mỗi phương pháp cần nắm vững các phần sau - Giải thuật sắp xếp. - Minh họa việc sắp xếp theo giải thuật. - Chương trình sắp xếp. - Đánh giá giải thuật. 2.1.2 Kiến thức cơ bản cần thiết Các kiến thức cơ bản cần thiết để học chương này bao gồm - Cấu trúc dữ liệu kiểu mẩu tin record và kiểu mảng array của các mẩu tin. - Kiểu dữ liệu trừu tượng danh sách và thủ tục xen một phần tử vào danh sách insert . - Kĩ thuật lập trình và lập trình đệ quy. 2.1.3 Tài liệu tham khảo A.V. Aho J.E. Hopcroft J.D. Ullman. Data Structures and Algorithms. Addison-Wesley. 1983. Chapter 8 . Jeffrey H Kingston Algorithms and Data Structures Addison-Wesley 1998. Chapter 9 . Đinh Mạnh Tường. Cấu trúc dữ liệu Thuật toán. Nhà xuất bản khoa học và kĩ thuật. Hà nội-2001. Chương 9 . Đỗ Xuân Lôi. Cấu trúc dữ liệu Giải thuật. 1995. Chương 9 . 2.1.4 Nội dung cốt lõi Trong chương này chúng ta sẽ nghiên cứu các vấn đề sau Bài toán sắp xếp. Một số giải thuật sắp xếp đơn giản. QuickSort HeapSort BinSort Nguyên Văn Linh Trang 18 Sưu tầm bởi www.daihoc.com.vn Giải thuật Sắp xếp 2.2 BÀI TOÁN SẮP XẾP 2.2.1 Tầm quan trọng của bài toán sắp xếp Sắp xếp một danh sách các đối tượng theo một thứ tự nào đó là một bài toán thường được vận dụng trong các ứng dụng tin học. Ví dụ ta cần sắp xếp danh sách thí sinh theo tên với thứ tự Alphabet hoặc sắp xếp danh sách sinh viên theo điểm trung bình với thứ tự từ cao đến thấp. Một ví dụ khác là khi cần tìm kiếm một đối tượng trong một danh sách các đối tượng bằng giải thuật tìm kiếm nhị phân thì danh sách các đối tượng này phải được sắp xếp trước đó. Tóm lại sắp xếp là một yêu cầu không thể thiếu trong khi thiết kế các phần mềm. Do đó việc nghiên cứu các phương pháp sắp xếp là rất cần thiết để vận dụng trong khi lập trình. 2.2.2 Sắp xếp trong và sắp xếp ngoài Sắp xếp trong là sự sắp xếp dữ liệu được tổ chức trong bộ nhớ trong của máy tính ở đó ta có thể sử