tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật: Tìm kiếm và sắp xếp - Đậu Ngọc Hà Dương

Bài giảng Cấu trúc dữ liệu và giải thuật: Tìm kiếm và sắp xếp - Đậu Ngọc Hà Dương có nội dung trình bày về tìm kiếm tuần tự và tìm kiếm nhị phân; sắp xếp bubble sort, selection sort, insert sort, quick sort, . Mời các bạn cùng tham khảo! | 1 TÌM KIẾM amp SẮP XẾP Bài giảng Cấu trúc dữ liệu và Giải thuật Nội d dung Tì kiếm Tìm kiế Tuần tự Nhị phân Sắp xếp Bubble sort Selection sort Insert sort Quick sort Tìm kiếm 3 Tìm kiếm duyệt một danh sách và lấy ra phần tử thoả tiêu chuẩn cho trước. Là thao tác phổ biến trên máy tính Tìm mẫu tin trong cơ sở dữ liệu Tìm kiếm thông tin trên Internet Khảo sát việc tìm kiếm trên mảng danh sách. Tìm kiếm 4 Giải thuật Input put Mảng A gồm n phần tử Giá trị x cần tìm Trả về Vị trí phần tử x trong A hoặc 1 nếu x không xuất hiện Thao tác cơ bản So sánh Tìm kiếm tuần tự 5 Giải thuật Giải thuật Lần lượt so sánh x với các phần tử của mảng A cho đến khi gặp được phần tử cần tìm hoặc hết mảng. Ví dụ A 1 25 6 5 2 37 40 x 6 x 6 1 25 6 5 2 37 40 x 6 1 25 6 5 2 37 40 x 6 1 25 6 5 2 37 40 Dừng Tìm kiếm tuần tự 6 Đánh giá Đánh giá thao tác so sánh Tốtnhất O 1 Hiếm khi xảy ra. Tại sao Xấu nhất O n Trung bình Giả sử dữ liệu phân bố đều xác suất bắt gặp x tại mỗi vị trí đều như nhau. Mỗi vòng lặp thực hiện 2 thao tác so sánh. Tại sao Số thao tác 2 1 2 n n 1 Độ phức tạp O n Tìm kiếm tuần tự 7 Phần tử lính canh Mỗi vòng lặp cần 2 thao tác so sánh Kiểm tra hết mảng Kiểm tra phần tử hiện tại có bằng x Phần tử lính canh đặt giá trị x vào cuối mảng không cần kiểm tra điều kiện hết mảng. Ví dụ A 1 25 5 2 37 x 6 1 25 5 2 37 6 Trả về ề n nếu nế không tìm thấ thấy Tìm kiếm nhịị phân p 8 Khi mảng gồm các phần tử được sắp sắp tận dụng điều kiện này để giảm số thao tác. Ý tưởng Xétphần tử giữa A m Nếu A m x trả về m Nếu A m gt x x tìm trong các phần tử bên trái của m Nếu A m lt x tìm trong các phần tử bên trái của m Tìm kiếm nhị phân 9 Ví dụ minh hoạ A 2 2 3 3 6 6 7 7 10 10 16 16 18 18 x 16 2 3 6 7 10 16 18 0 1 2 3 4 5 6 4 5 6 2 3 6 7 10 16 18 Tìm kiếm nhị phân Chương trình 10 int BinarySearch int a int n int x int l 0 r n-1 while l Tìm kiếm nhị phân 11 Bài tập Thực hiện việc tìm kiếm đối với các bài tập sau A 1 2 6 26 28 37 40 x 40 A 1 2 6 26 28 37 40 x -7 Tìm kiếm nhị phân 12 Đánh giá Mỗi lần lặp