tailieunhanh - Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 2 - ThS. Phạn Nguyệt Thuần

Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 2 - Tìm kiếm và sắp xếp nội do ThS. Phạn Nguyệt Thuần trình bày. Bài giảng trình bày về các nội dung: Các giải thuật tìm kiếm nội, các giải thuật sắp xếp nội. nội dung chi tiết tài liệu. | CHƢƠNG 2 TÌM KiẾM VÀ SẮP XẾP NỘI 1 Nội dung Các giải thuật tìm kiếm nội 1. Tìm kiếm tuyến tính 2. Tìm kiếm nhị phân Các giải thuật sắp xếp nội 1. Đổi chỗ trực tiếp – Interchange Sort 2. Chọn trực tiếp – Selection Sort 3. Nổi bọt – Bubble Sort 2 Nội dung 4. Chèn trực tiếp – Insertion Sort 5. Shell Sort 6. Heap Sort 7. Quick Sort 3 Nhu cầu tìm kiếm và sắp xếp Thao tác tìm kiếm đƣợc sử dụng nhiều nhất trong các hệ lƣu trữ và quản lý dữ liệu. Do dữ liệu lớn nên tìm ra giải thuật tìm kiếm nhanh chóng là mối quan tâm hàng đầu. Để đạt đƣợc điều này dữ liệu phải đƣợc tổ chức theo một thứ tự nào đó thì việc tìm kiếm sẽ nhanh chóng và hiệu quả hơn, vì vậy nhu cầu sắp xếp dữ liệu cũng đƣợc lƣu ý. Tóm lại, bên cạnh những giải thuật tìm kiếm thì các giải thuật sắp xếp dữ liệu không thể thiếu trong hệ quản lý thông tin trên máy tính. 4 Các giải thuật tìm kiếm Có 2 giải thuật thƣờng đƣợc áp dụng: Tìm tuyến tính và tìm nhị phân. Để đơn giản cho việc minh họa, ta đặc tả nhƣ sau: a1 a2 a3 a4 a5 an-1 aN ◦ Tập dữ liệu đƣợc lƣu trữ là dãy số a1, a2, . ,aN. ◦ Giả sử chọn cấu trúc dữ liệu mảng để lƣu trữ dãy số này trong bộ nhớ chính, có khai báo: int a[N]; ◦ Khoá cần tìm là x, đƣợc khai báo nhƣ sau: int .