Bài giảng Cấu trúc dữ liệu và giải thuật: Các thuật toán tìm kiếm và sắp xếp cơ bản - Lê Thị Ngọc Hạnh

Bài giảng Cấu trúc dữ liệu và giải thuật: Các thuật toán tìm kiếm và sắp xếp cơ bản gồm có những nội dung chính sau: Giới thiệu các giải thuật tìm kiếm, tìm kiếm tuần tự, tìm kiếm nhị phân, đánh giá và tổng kết. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Các thuật toán tìm kiếm và sắp xếp cơ bản - Lê Thị Ngọc Hạnh CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 CÁC THUẬT TOÁN TÌM KIẾM VÀ SẮP XẾP CƠ BẢNCác thuật toán tìm kiếm và sắp xếp cơ bản 8/27/2015 Nội dung trình bày 2 Giới thiệu các giải thuật tìm kiếm Tìm kiếm tuần tự Tìm kiếm nhị phân Đánh giá và tổng kếtCác thuật toán tìm kiếm và sắp xếp cơ bản 8/27/20151. Giới thiệu thuật toán tìm kiếm 3 Tìm kiếm là thao tác rất phổ biến trong cuộc sống hàng ngày. Các loại tìm kiếm:  Tìm kiếm tuần tự (Sequential/ Linear Search)  Tìm kiếm nhị phân (Binary Search)  …… Mục tiêu:  Tìm hiểu về 2 giải thuật tìm kiếm cơ bản.  Phân tích thuật toán để lựa chọn thuật toán phù hợp với dữ liệu đầu vào.Các thuật toán tìm kiếm và sắp xếp cơ bản 8/27/2015 2.1. Tìm kiếm tuần tự - Vét cạn 4 Ý tưởng: So sánh x lần lượt với các phần tử của mảng A cho đến khi gặp được phần tử có giá trị x cần tìm, hoặc đã tìm đến hết mảng mà không thấy x. Minh họa: x = 2827 Có x trong Không tìm thấy x mảngmảng trong 25 7 3 12 27 5 9 8 61 27 28 27 28 27 28 27 28 27 28 28 28 28 28 28Các thuật toán tìm kiếm và sắp xếp cơ bản 8/27/2015 2.1. Tìm kiếm tuần tự - Vét cạn 5 Input:  Mảng A.  n phần tử.  Giá trị x cần tìm Output:  Nếu x xuất hiện trong A, trả về 1.  Ngược lại, trả về 0.Các thuật toán tìm kiếm và sắp xếp cơ bản 8/27/2015 2.1. Tìm kiếm tuần tự - Vét cạn 6 Bước 1: Bắt đầu từ phần tử đầu tiên: i = 0 Bước 2: so sánh i và n  Nếu chưa hết mảng (i=n), kết thúc.Trả về 0. Bước 3: So sánh giá trị A[i] với x  Nếu A[i] bằng x: kết thúc. Trả về 1.  Nếu A[i] khác x, tăng i thêm 1 và quay lại bước 2.Các thuật toán tìm kiếm và sắp xếp cơ bản 8/27/2015 2.1. Tìm kiếm tuần tự - Vét cạn 7 Bắt đầuLưu đồthuật toán Nhập A, n, x i=0 Đ Kết i>=n thúc S Đ A[i] = x S i = i+1Các thuật toán tìm kiếm và sắp xếp cơ bản 8/27/2015 2.1. Tìm kiếm tuần tự - Vét cạn 8 Mỗi vòng lặp, có 2 điều kiện cần kiểm tra:  Kiểm tra đã duyệt hết mảng? (bước 2)  Kiểm tra phần tử hiện tại có bằng x?(bước 3) Số phép so sánh trung bình: 2(1+2+3+…+n)/n = n+1  Số phép so sánh tăng/giảm tuyến tính theo sốphần tử.Các thuật toán tìm kiếm và sắp xếp cơ bản 8/27/2015 2.1. Tìm kiếm tuần tự - Vét cạn 9 Độ phức tạp của thuật toán:  Tốt nhất: O(1)  Trung bình: O(n)  Xấu nhất: O(n)Các thuật toán tìm kiếm và sắp xếp cơ bản 8/27/2015 2.2. Tìm kiếm tuần tự - Lính canh 10 Có thể bỏ qua việc kiểm tra điều kiện cuối mảng bằng cách dùng “lính canh”. Lính canh là phần tử có giá trị bằng với phần tử cần tìm và được đặt ở cuối mảng.Các thuật toán tìm kiếm và sắp xếp cơ bản 8/27/2015 2.2. Tìm kiếm tuần tự - Lính canh 11 Ví dụ: A = {25, 6, 18, 4}; x = 7(1) 25 6 18 4 7 (2) 25 6 18 4 7 x=7 x=7(3) 25 6 18 4 7 (4) 25 6 18 4 7 ...