Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 trình bày nội dung về tìm kiếm và sắp xếp nội: Nhu cầu tìm kiếm, sắp xếp dữ liệu ; Các giải thuật tìm kiếm nội; Các giải thuật sắp xếp nội. Mời các bạn tham khảo nội dung chi tiết. | CHƢƠNG 2 TÌM KIẾM VÀ SẮP XẾP NỘI CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 1 Nội Dung Nhu cầu tìm kiếm sắp xếp dữ liệu 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ẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 Các giải thuật sắp xếp nội 1. Chọn trực tiếp Selection Sort 2. Chèn trực tiếp Insertion Sort 3. Chèn nhị phân 2 Nội Dung Tt 4. Đổi chỗ trực tiếp Interchange Sort 5. Nổi bọt Bubble Sort 6. Shaker Sort 7. Shell Sort CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 8. Heap Sort 9. Quick Sort 10. Merge Sort 11. Radix Sort 3 Nhu Cầu Tìm Kiếm và Sắp Xếp Trong thực tế khai thác dữ liệu hầu như lúc nào cũng phải thực hiện thao tác tìm kiếm. Việc tìm kiếm nhanh hay chậm tùy thuộc vào trạng thái và trật tự của dữ liệu trên đó. Để tìm kiếm dữ liệu dễ dàng và nhanh chóng CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 trước khi thao tác thì dữ liệu trên mảng và tập tin đã có thứ tự. Thao tác sắp xếp dữ liệu là một trong những thao tác cần thiết. 4 Bài Toán Tìm Kiếm Cho danh sách có n phần tử a0 a1 a2 an-1. Để đơn giản trong việc trình bày giải thuật ta dùng mảng 1 chiều a để lưu danh sách các phần tử nói trên trong bộ nhớ chính. Tìm phần tử có khoá bằng X trong mảng CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 Giải thuật tìm kiếm tuyến tính tìm tuần tự Giải thuật tìm kiếm nhị phân Lưu ý Trong quá trình trình bày thuật giải ta dùng ngôn ngữ lập trình C. 5 Tìm Kiếm Tuyến Tính Ý tƣởng So sánh X lần lượt với phần tử thứ 1 thứ 2 của mảng a cho đến khi gặp được khóa cần tìm hoặc tìm hết mảng mà không thấy. Các bƣớc tiến hành Bước 1 Khởi gán i 0 CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 Bước 2 So sánh a i với giá trị x cần tìm có 2 khả năng a i x tìm thấy x. Dừng a i x sang bước 3 Bước 3 i i 1 Xét tiếp phần tử kế tiếp trong mảng Nếu i N Hết mảng. Dừng Ngược lại Lặp lại bước 2 6 Thuật Toán Tìm Kiếm Tuyến Tính Hàm trả về 1 nếu tìm thấy ngược lại trả về 0 int LinearSearch int a int n int x int i 0 while i Minh Họa Thuật Toán Tìm Kiếm Tuyến Tính X 6 Tìm thấy 6 tại vị trí 4 i CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 2 8 5 1 6 4 6 0 1 2
