Chương 5 Sắp xếp (Sorting) Heap Sort Quick Sort William A. Martin, Sorting. ACM Computing Surveys, Vol. 3, Nr 4, Dec 1971, pp. 147-174. " ...The bibliography appearing at the end of this article lists 37 sorting algorithms and 100 books and papers on sorting published in the last 20 years... Suggestions are made for choosing the algorithm best suited to a given situation." D. Knuth: 40% thời gian hoạt động của các máy tính là dành cho sắp xếp! KHMT - ĐHBKHN Bài giảng của PGS.TS. NGUYỄN ĐỨC NGHĨA Khoa học Máy tính Đại học Bách khoa Hà nội KHMT - ĐHBKHN NỘI DUNG 5.1. Bài toán sắp xếp 5.2. Ba thuật toán sắp xếp cơ bản 5.3. Sắp xếp trộn (Merge Sort) 5.4. Sắp xếp nhanh (Quick Sort) 5.5. Sắp xếp vun đống (Heap Sort) KHMT - ĐHBKHN 3 5.1. Bài toán sắp xếp 5.1.1. Bài toán sắp xếp 5.1.2. Giới thiệu sơ lược về các thuật toán sắp xếp KHMT - ĐHBKHN 4 5.1.1. Bài toán sắp xếp Sắp xếp (Sorting) – Là quá trình tổ chức lại họ các dữ liệu theo thứ tự giảm dần hoặc tăng dần (ascending or descending order) Dữ liệu cần sắp xếp có thể là – Số nguyên (Integers) – Xâu ký tự (Character strings) – Đối tượng (Objects) Khoá sắp xếp (Sort key) – Là bộ phận của bản ghi xác định thứ tự sắp xếp của bản ghi trong họ các bản ghi. Ta cần sắp xếp các bản ghi theo thứ tự của các khoá. KHMT - ĐHBKHN 5 5.1.1. Bài toán sắp xếp Chú ý: Việc sắp xếp tiến hành trực tiếp trên bản ghi đòi hỏi di chuyển vị trí bản ghi, có thể là thao tác rất tốn kém. Vì vậy, người ta thường xây dựng bảng khoá gồm các bản ghi chỉ có hai trường là (khoá, con trỏ) – trường "khoá" chứa giá trị khoá, – trường "con trỏ" để ghi địa chỉ của bản ghi tương ứng. Việc sắp xếp theo khoá trên bảng khoá không làm thay đổi bảng chính, nhưng trình tự các bản ghi trong bảng khoá cho phép xác định trình tự các bản ghi trong bảng chính. KHMT - ĐHBKHN 6 5.1.1. Bài toán sắp xếp Ta có thể hạn chế xét bài toán sắp xếp dưới dạng sau đây: Input: Dãy n số A = (a1, a2, …, an) Output: Một hoán vị (sắp xếp lại) (a'1,…, a