tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật: Bài 13 - Hoàng Thị Điệp (2014)

Bài giảng "Cấu trúc dữ liệu và giải thuật - Bài 13: Các thuật toán sắp xếp" cung cấp cho người học các kiến thức: Bài toán sắp xếp, sắp xếp xen vào, sắp xếp trộn, sắp xếp nhanh, sắp xếp sử dụng cây thứ tự bộ phận, sắp xếp đếm, sắp xếp cơ số. | Tài liệu tham khảo: Bài giảng SMA 5503 Introduction to Algorithms. 2001-5 Erik D. Demaine and Charles E. Leiserson. Bài 13: Các thuật toán sắp xếp Giảng viên: Hoàng Thị Điệp Khoa Công nghệ Thông tin – Đại học Công Nghệ Cấu trúc dữ liệu và giải thuật HKI, 2013-2014 Nội dung chính 1. 2. 3. 4. 5. 6. 7. 2 Bài toán sắp xếp Sắp xếp xen vào Sắp xếp trộn Sắp xếp nhanh Sắp xếp sử dụng cây thứ tự bộ phận Sắp xếp đếm Sắp xếp cơ số diepht@vnu Bài toán sắp xếp Lí do: Một trong những bài toán được nghiên cứu lâu đời nhất trong CNTT Chứa nhiều kĩ thuật về thuật toán Input: dãy số Output: 1 hoán vị của input thỏa mãn a1’<= a2’<= . <= an’ Ý nghĩa? Bài toán tìm kiếm Bài toán phát hiện phần tử lặp 3 diepht@vnu Ví dụ bài toán tìm kiếm x=5 A = (3, 1, 4, 15, 9, 26, 53, 58, 97, 93, 23, 8, 46, 26, 4, 33, 8, 3, 2) B = (1, 2, 3, 3, 4, 4, 8, 8, 9, 15, 23, 26, 26, 33, 46, 53, 58, 93, 97) x có trong A? x có trong B? 4 INT2203/w13 diepht@vnu Ví dụ bài toán phát hiện phần tử lặp A = (3, 1, 4, 15, 9, 26, 53, 58, 97, 93, 23, 8, 46, 26, 4, 33, 8, 3, 2) B = (1, 2, 3, 3, 4, 4, 8, 8, 9, 15, 23, 26, 26, 33, 46, 53, 58, 93, 97) Các giá trị xuất hiện hơn 1 lần trong A? Các giá trị xuất hiện hơn 1 lần trong .