Bài giảng Cấu trúc dữ liệu và giải thuật: Phần 2 trình bày về các thuật toán sắp xếp và tìm kiếm. Các thuật toán này cùng với các kỹ thuật được sử dụng trong đó được coi là các kỹ thuật cơ sở cho lập trình máy tính. Các thuật toán được xem xét bao gồm các lớp thuật toán đơn giản và cả các thuật toán cài đặt phức tạp nhưng có thời gian thực hiện tối ưu. Mời các bạn cùng tham khảo để nắm nội dung chi tiết. | HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG - - KHOA CÔNG NGHỆ THÔNG TIN BÀI GIẢNG CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT NGUYỄN DUY PHƯƠNG HàNội 2013 CHƯƠNG 7 SẮP XẾP VÀ TÌM KIẾM Sắp xếp và tìm kiếm là các vấn đề rất cơ bản trong tin học cũng như trong thực tiễn. Chương 7 giới thiệu các phương pháp sắp xếp và tìm kiếm thông dụng nhất bao gồm các giải thuật từ đơn giản đến phức tạp. Đối với các giải thuật sắp xếp các phương pháp sắp xếp đơn giản được trình bày bao gồm sắp xếp chọn sắp xếp chèn sắp xếp nổi bọt. Các phương pháp sắp xếp phức tạp và hiệu quả hơn được xem xét là giải thuật sắp xếp nhanh quick sort sắp xếp vun đống heap sort và sắp xếp trộn merge sort . Với mỗi phương pháp sắp xếp ngoài việc trình bày các bước thực hiện thuật toán độ phức tạp của giải thuật cũng được tính toán và đánh giá. Đối với các phương pháp tìm kiếm ngoài phương pháp tìm kiếm tuần tự đơn giản các phương pháp tìm kiếm phức tạp và hiệu quả hơn cũng được xem xét là tìm kiếm nhị phân và tìm kiếm bằng cây nhị phân tìm kiếm. Để học tốt chương này sinh viên cần nghiên cứu kỹ các bước thực hiện các thuật toán và lấy ví dụ cụ thể sau đó thực hiện từng bước trên ví dụ. BÀI TOÁN SẮP XẾP Sắp xếp là quá trình bố trí lại các phần tử của 1 tập hợp theo thứ tự nào đó. Mục đích chính của sắp xếp là làm cho thao tác tìm kiếm phần tử trên tập đó được dễ dàng hơn. Ví dụ về tập các đối tượng được sắp phổ biến trong thực tế là danh bạ điện thoại được sắp theo tên các từ trong từ điển được sắp theo vần sách trong thư viện được sắp theo mã số theo tên .. Nhìn chung có rất nhiều thao tác xử lý dữ liệu cần đến việc sắp xếp các phần tử dữ liệu theo trình tự nào đó. Trên thực tế sắp xếp là một thao tác khá đơn giản. Tuy nhiên như chúng ta sẽ thấy có rất nhiều giải thuật sắp xếp khác nhau từ đơn giản tới phức tạp. Và các kỹ thuật được sử dụng trong các giải thuật sắp xếp này được nghiên cứu và phân tích nhiều hơn là chính bản thân giải thuật sắp xếp. Các kỹ thuật này được coi là cơ sở để xây dựng nhiều giải thuật
