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

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 8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản 1 Nội dung trình bày 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 8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản 2 Đánh giá và tổng kết 8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản 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. 1. Giới thiệu thuật toán tìm kiếm 2.1. Tìm kiếm tuần tự - Vét cạn 8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bả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: 25 7 3 12 27 5 9 8 61 x = 27 27 27 27 27 27 Có x trong mảng 8 8 8 8 8 8 28 28 28 28 Không tìm thấy x trong mảng 28 2.1. Tìm kiếm tuần tự - Vét cạn 8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bả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. 8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bả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), sang bước 3;  Nếu đã 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. 2.1. Tìm kiếm tuần tự - Vét cạn 8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản 7 Bắt đầu Nhập A, n, x i = 0 i>=n A[i] = x i = i+1 Kết thúc Lưu đồ thuật toán Đ S S Đ 2.1. Tìm kiếm tuần tự - Vét cạn 8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bả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ử. 2.1. Tìm kiếm tuần tự - Vét cạn 8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bả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) 2.1. Tìm kiếm tuần tự - Vét cạn 8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản 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. 2.2. Tìm kiếm tuần tự - Lính canh 8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản 11 Ví dụ: A = {25, 6, 18, 4}; x = 7 25 6 18 4 7 x=7 25 6 18 4 7 25 6 18 4 7 25 6 18 4 7 x=7 x=7 x=7 x=7 25 6 18 4 7 i = 4 (i>n) (1) (2) (3) (4) (5) 2.2. Tìm kiếm tuần tự - Lính canh 8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản 12  Bước 1: Bắt đầu từ phần tử đầu tiên: i = 0  Bước 2: So sánh giá trị A[i] với giá trị x  Nếu A[i] khác x, tăng i thêm 1 và quay lại bước 2.  Nếu A[i] bằng x: • Nếu i<n: kết thúc chương trình và trả về 1 • Nếu i>=n: kết thúc, trả về 0. 2.2. Tìm kiếm tuần tự - Lính canh Task 8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản 13  Task 1: Cài đặt thuật toán tìm kiếm theo cách vét cạn và sử dụng lính canh.  Task 2: Xây dựng thuật toán và cài đặt chương trình tìm những vị trí mà x xuất hiện trong mảng cho trước.  Task 3: Xây dựng thuật toán và cài đặt chương trình tìm xem trong mảng cho trước có phần tử nào là số chẵn hay không? 3. Tìm kiếm nhị phân (Binary Search) 8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản 14 Thuật toán tìm kiếm nhị phân 8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản 15  Với dãy A được sắp xếp tuần tự (tăng/giảm) thì độ phức tạp của thuật toán tìm kiếm tuần tự không đổi.  Tận dụng thông tin của mảng đã được sắp xếp để giới hạn vùng tìm kiếm của giá trị cần tìm trong mảng.  Thuật toán tìm kiếm nhị phân. 8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản 16 Thuật toán tìm kiếm nhị phân  Input:  Mảng A với n phần tử đã được sắp xếp.  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. 8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản 17 Ý tưởng:  So sánh x với giá trị của phần tử chính giữa của mảng A.  Nếu x là phần tử chính giữa thì dừng.  Nếu không, xác định xem x thuộc nửa trái hay nửa phải của phần tử chính giữa.  Lặp lại 2 bước trên với nửa đã được xác định. Thuật toán tìm kiếm nhị phân 8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản 18  Bước 1: left = 0; right = n-1;  Bước 2: mid = (left + right)/2; So sánh A[mid] với x có 3 khả năng:  A[mid] = x: Tìm thấy. Dừng.  A[mid] > x: right = mid - 1;  A[mid] < x: left = mid + 1;  Bước 3: Nếu left <= right: lặp lại Bước 2. Ngược lại: Dừng. Thuật toán tìm kiếm nhị phân Index 0 1 2 3 4 5 6 A[i] 4 8 15 17 32 59 72 8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản 19 Minh họa: A[] = {4, 8, 15, 17, 32, 59, 72}, x = 8. Thuật toán tìm kiếm nhị phân x<A[3] x=A[1] Đã tìm thấy x trong A, kết thúc Lần 1 right mid left Lần 2 =(0+6)/2=3 2 1i 8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản 20 Minh họa: A[] = {4, 8, 15, 17, 32, 59, 72}, Index 0 1 2 3 4 5 6 A[i] 4 8 15 17 32 59 72 Thuật toán tìm kiếm nhị phân x>A[3] left right l f mid x>A[5] left right x=A[6] Tìm thấy x trong A, kết thúc Lần 1 Lần 2 Lần 3 mid=(0+6)/2=3 4 56 6 x = 72 3 > Không tìm hấy x trong A, kết thúc left>right 8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản 21 Phân tích thuật toán:  Mỗi lần lặp thì chiều dài của mảng con giảm đi ½ so với chiều dài mảng trước đó.  Chia mảng A đến khi còn 1 phần tử: (((((n/2)/2)/2))/2) = n/2k n/2k =1; n = 2k ; log2n= log2n; k = log2n Số lần thực hiện vòng lặp while khoảng k lần, mỗi vòng lặp thực hiện 1 phép so sánh. Thuật toán tìm kiếm nhị phân 8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản 22 Phân tích thuật toán:  Trường hợp tốt nhất: k = 1  x là phần tử chính giữa của mảng.  Trường hợp xấu nhất: k = log2n  x không thuộc mảng hoặc x là phần tử thuộc biên của mảng.  Số phép so sánh tăng theo hàm logarit. Thuật toán tìm kiếm nhị phân 8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản 23 Độ phức tạp của tìm kiếm nhị phân: Trường hợp tốt nhất: O(1) Trường hợp trung bình: O(log2n/2) Trường hợp xấu nhất: O(log2n) Thuật toán tìm kiếm nhị phân So sánh hiệu suất 8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản 24 So sánh trường hợp xấu nhất của 2 thuật toán tìm kiếm: Kích thước mảng Trường hợp xấu nhất Tuần tự Nhị phân 100.000 100.000 16 200.000 200.000 17 400.000 400.000 18 800.000 800.000 19 1.600.000 1.600.000 20 4. Tổng kết 8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản 25  Thuật toán tuần tự:  Tìm kiếm cho đến khi tìm thấy giá trị cần tìm hoặc hết mảng.  Hiệu suất của tìm kiếm tuần tự trong trường hợp xấu nhất là 1 hàm tuyến tính theo số phần tử của mảng.  Tìm kiếm nhị phân:  Dùng kết quả của phép so sánh để thu hẹp vùng tìm kiếm kế tiếp.  Hiệu suất của tìm kiếm nhị phân là một hàm logarit theo số phần tử của mảng. LinearSearch 8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản 26 bool LinearSearch(int a[], int n, int x) { int kq = true; for(int i=0; i<n;i++) { if(a[i]==x) return kq; kq = false; } return kq; } BinarySearch 8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản 27 Bool BinarySearch(int a[], int n, int x) { int left=0, right=n-1,mid; bool kq=true; do{ mid=(left+right)/2; if(x==a[mid]) return kq; else if(x<a[mid]) right=mid-1; else left=mid+1; } while(left<right); return kq=false; } 8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản 28 1. Sử dụng thuật toán tìm kiếm tuần tự trên mảng 1 chiều, cài đặt các hàm xử lý các yêu cầu sau: - Đếm số lượng của x có trong mảng. - Xuất ra các vị trí của x trong mảng. 2. Sử dụng thuật toán tìm kiếm nhị phân với mảng bất kỳ.