Giáo trình giải thuật - tìm kiếm và sắp xếp

* Tìm kiếm và sắp xếp là 2 bài toán rất kinh điển trong tin học* Tìm kiếm là thao tác được thực hiện nhiều nhất trong các hệ thống lưu trữ và quản lý dữ liệu - Tra từ điển, tìm kiếm sinh viên, tìm kiếm khách hàng... - Thao tác tìm kiếm sẽ thực hiện hiệu quả khi dữ liệu được tổ chức theo một trật tự nào đó.
Nội dung trích xuất từ tài liệu:
Giáo trình giải thuật - tìm kiếm và sắp xếp 12/6/2010 Tìm kiếm và sắp xếp GVGD: Trương Phước Hải LOGO Nội dung 1. Bài toán tìm kiếm và sắp xếp 2. Một số phương pháp tìm kiếm 3. Một số phương pháp sắp xếp 2 Bài toán tìm kiếm và sắp xếp Tìm kiếm và sắp xếp là 2 bài toán rất kinh điển trong tin học Tìm kiếm là thao tác được thực hiện nhiều nhất trong các hệ thống lưu trữ và quản lý dữ liệu Tra từ điển, tìm kiếm sinh viên, tìm kiếm khách hàng, …  Thao tác tìm kiếm sẽ thực hiện hiệu quả khi dữ liệu được tổ  chức theo một trật tự nào đó Sắp xếp dữ liệu cũng là yêu cầu cần phải có trong các hệ thống thông tin quản lý, … 3 1 12/6/2010 Bài toán tìm kiếm và sắp xếp Bài toán tìm kiếm Cho một tập gồm N phần tử dữ liệu. Cho biết sự tồn tại  hoặc chỉ ra vị trí xuất hiện của một phần tử nào đó với thông tin xác định được cho trước Bài toán sắp xếp Cho một tập gồm N phần tử dữ liệu. Sắp xếp các phần tử  dữ liệu có thứ tự (tăng hoặc giảm dần) theo một tiêu chí cho trước 4 Bài toán tìm kiếm và sắp xếp Tính hiệu quả của các phương pháp tìm kiếm và sắp xếp phụ thuộc vào tính chất của CTDL Các phương pháp tìm kiếm và sắp xếp cũng phụ thuộc vào dữ liệu lưu trữ ở bộ nhớ trong hay bộ nhớ ngoài Các giải thuật được trình bày dành cho dữ liệu lưu trữ ở bộ nhớ trong 5 Nội dung 1. Bài toán tìm kiếm và sắp xếp 2. Một số phương pháp tìm kiếm 3. Một số phương pháp sắp xếp 6 2 12/6/2010 Bài toán tìm kiếm Bài toán Cho mảng 1 chiều A gồm N phần tử nguyên. Cho biết số  nguyên x có tồn tại trong A hay không? Nếu có thì cho biết 1 vị trí xuất hiện của x trong A Input: Mảng A gồm N phần tử nguyên, số nguyên x  Ouput:  p ≥ 0 là vị trí xuất hiện của x trong A  p < 0 nếu x không tồn tại trong A  7 Tìm kiếm tuần tự Ý tưởng Xét lần lượt từng phần tử trong toàn bộ không gian tìm  kiếm để tìm ra 1 phần tử thỏa tiêu chí hoặc không tìm thấy phần tử nào thỏa tiêu chí Thao tác dừng lại ngay khi tìm thấy phần tử đầu tiên thỏa  tiêu chí hoặc xét hết tất cả phần tử 8 Tìm kiếm tuần tự Giải thuật Bắt đầu N, A[0], A[1], .., A[N-1], x i=0 F T i 12/6/2010 Tìm kiếm tuần tự Cài đặt int LinearSearch(int A[], int N, int x) { for (int i = 0; i < N; i++) { if (A[i] == x) return i; } return -1; } 10 Tìm kiếm tuần tự Đánh giá Dựa trên số phép so so sánh của giải thuật  Trường hợp Số phép so sánh Diễn giải Tốt nhất 1 x nằm ở đầu mảng Xấu nhất N x không thuộc mảng Độ phức tạp tính toán cấp N: T(N) = O(N)  11 Tìm kiếm nhị phân Ý tưởng Điều kiện thực thi giải thuật: không gian tìm kiếm phải  được sắp thứ tự (tăng dần hoặc giảm dần) theo tiêu chí tìm kiếm Dựa vào tiêu chí có thứ tự để thu hẹp một nửa không gian  tìm kiếm sau mỗi bước thực hiện 12 4 12/6/2010 Tìm kiếm nhị phân Giải thuật Bước 1: đặt L = 0, R = N – 1 (L: đầu dãy; R: cuối dãy)  Bước 2:   Nếu L < R đúng thì đến bước 3  Ngược lại đến bước 4 Bước 3:   Đặt M = (L + R)/2 (M: vị trí giữa dãy)  Trường hợp x = A[M] thì tìm thành công. Đến bước 4  Trường hợp x < A[M] thì đặt R = M – 1  Trường hợp A[M] < x thì đặt L = M + 1  Quay về bước 2 Bước ...