Pp tìm kiếm sắp xếp

Các giải thuật
tìm kiếm nội
Tìm kiếm tuyến tính
Tìm kiếm nhị phân
Cấu trúc Dữ liệu - Tìm kiếm và Sắp xếp
2
Tìm kiếm là thao tác thường được thực hiện nhất.
Dữ liệu đã được sắp xếp => tìm nhanh hơn.
=> Vấn đề:
Tìm kiếm nhanh.
Sắp xếp nhanh.
Nhu cầu tìm kiếm và sắp xếp dữ liệu trong một hệ thống thông tin.
Cấu trúc Dữ liệu - Tìm kiếm và Sắp xếp
3
Các giải thuật tìm kiếm nội
Bài toán:
Chọn cấu trúc dữ liệu mảng (a) để lưu trữ dãy số a1, a2 ,.,an .
Tìm một số nguyên x trong mảng a.
Có 2 giải thuật tìm kiếm:
Tìm kiếm tuyến tính.
Tìm kiếm nhị phân.
Tìm kiếm tuyến tính
Cấu trúc Dữ liệu - Tìm kiếm và Sắp xếp
5
Tìm tu?n t? (tìm tuy?n tính)
Ý tưởng:

Thuật toán tiến hành so sánh x lần lượt với phần tử thứ nhất, thứ hai,. của mảng a cho đến khi gặp được phần tử có khóa cần tìm, hoặc đã tìm hết mảng mà không thấy x.
Cấu trúc Dữ liệu - Tìm kiếm và Sắp xếp
6
Tìm kiếm tuyến tính
Bước 1: i = Vị trí đầu;
Bước 2: Nếu a[i] = x : Tìm thấy. Dừng, vị trí xuất hiện: i
Bước 3 : i = Vị trí kế(i);// xét tiếp phần tử kế trong mảng
Bước 4: Nếu i >Vị trí cuối: //Hết mảng
Không tìm thấy. Dừng.
Ngược lại: Lặp lại Bước 2.
Cấu trúc Dữ liệu - Tìm kiếm và Sắp xếp
7
Tìm kiếm tuyến tính
(sequential search)
5
Khóa tìm
7
13
5
21
6
2
8
15
Vị trí = 2
Tìm thành công
Số lần so sánh: 3
Cấu trúc Dữ liệu - Tìm kiếm và Sắp xếp
8
Tìm kiếm tuyến tính
(Khoâng tìm thaáy)
9
7
13
5
21
6
2
8
15
Không tìm thấy
Số lần so sánh: 8
Khóa tìm
Cấu trúc Dữ liệu - Tìm kiếm và Sắp xếp
9
Tìm kiếm tuyến tính
int LinearSearch(int a[], int n, int x)
{
int i=0;
while(i if (i return -1; // tìm hết mảng nhưng không có x
}
Cấu trúc Dữ liệu - Tìm kiếm và Sắp xếp
10
Tìm kiếm tuyến tính
Cải tiến cài đặt: dùng phương pháp “lính canh”
Đặt thêm một phần tử có giá trị x vào cuối mảng
Bảo đảm luôn tìm thấy x trong mảng
Sau đó dựa vào vị trí tìm thấy để kết luận.
Cấu trúc Dữ liệu - Tìm kiếm và Sắp xếp
11
Tìm kiếm tuyến tính
int LinearSearch(int a[], int n, int x)
{
int i=0;
// mảng gồm N phần tử từ a[0]..a[N-1]
a[n] = x; // thêm lính canh vào cuối dãy
while(a[i]!=x) i++;
if (i return -1; // tìm hết mảng nhưng không có x
}
Cấu trúc Dữ liệu - Tìm kiếm và Sắp xếp
12
Tìm kiếm tuyến tính
Đánh giá giải thuật:





Vậy giải thuật tìm tuần tự có độ phức tạp tính toán cấp n: T(n) = O(n)
Cấu trúc Dữ liệu - Tìm kiếm và Sắp xếp
13
Tìm kiếm tuyến tính
Nhận xét:
Giải thuật tìm tuyến tính không phụ thuộc vào thứ tự của các phần tử trong danh sách, do vậy đây là phương pháp tổng quát nhất để tìm kiếm trên một danh sách bất kỳ.
Một thuật toán có thể được cài đặt theo nhiều cách khác nhau, kỹ thuật cài đặt ảnh hưởng đến tốc độ thực hiện của thuật toán.
Tìm kiếm nhị phân
Cấu trúc Dữ liệu - Tìm kiếm và Sắp xếp
15
Tìm kiếm nhị phân
Đối với những dãy đã có thứ tự (giả sử thứ tự tăng ), các phần tử trong dãy có quan hệ
a[i-1]  a[i]  a[i+1]
Nếu x > a[i] thì x chỉ có thể xuất hiện trong đoạn [a[i+1] ,a[N]] của dãy
Nếu x < a[i] thì x chỉ có thể xuất hiện trong đoạn [a[0] ,a[i-1]] của dãy .
Cấu trúc Dữ liệu - Tìm kiếm và Sắp xếp
16
Tìm kiếm nhị phân
Ý tưởng của giải thuật là tại mỗi bước tiến hành so sánh x với phần tử nằm ở vị trí giữa của dãy tìm kiếm hiện hành, dựa vào kết quả so sánh này để quyết định giới hạn dãy tìm kiếm ở bước kế tiếp là nửa trên hay nửa dưới của dãy tìm kiếm hiện hành
Cấu trúc Dữ liệu - Tìm kiếm và Sắp xếp
17
Tìm kiếm nhị phân
Bước 1: left = VTĐ; right = VTC;
Bước 2: Trong khi left  right lặp: //đoạn tìm kiếm chưa rỗng
Bước 21: mid = (left+right)/2; // lấy mốc so sánh
Bước 22: Nếu a[mid] = x: //Tìm thấy.
Dừng, vị trí xuất hiện: mid
Bước 23: Nếu a[mid] > x: //tìm x trong dãy con aleft .. amid -1
right = mid - 1;
Ngược lại //tìm x trong dãy con amid +1 .. aright
left = mid + 1;
//Hết lặp
Bước 3: Dừng, không tìm thấy.
Cấu trúc Dữ liệu - Tìm kiếm và Sắp xếp
18
Ví d?: Tìm nh? ph�n
10
Target key
2
5
8
10
12
13
15
18
21
24
position = 3
return success
Số lần so sánh: 7
Khóa cần tìm không bằng
Khóa cần tìm nhỏ hơn
Khóa cần tìm lớn hơn
Khóa cần tìm bằng
Cấu trúc Dữ liệu - Tìm kiếm và Sắp xếp
19
Tìm kiếm nhị phân
int BinarySearch(int a[],int n,int x )
{
int left =0, right = n-1, mid;
while (left <= right)
{
mid = (left + right)/2;
if (x == a[mid])
return mid;//Tìm thấy x tại mid
if (x < a[mid]) right = mid -1;
else left = mid +1;
}
return -1; // trong dãy không có x
}
Cấu trúc Dữ liệu - Tìm kiếm và Sắp xếp
20
Tìm kiếm nhị phân
Đánh giá giải thuật:





Giải thuật tìm nhị phân có độ phức tạp tính toán cấp logn:
T(n) = O(log 2 n)
Cấu trúc Dữ liệu - Tìm kiếm và Sắp xếp
21
Tìm kiếm nhị phân
Nhận xét:    
Giải thuật tìm nhị phân dựa vào quan hệ giá trị của các phần tử mảng để định hướng trong quá trình tìm kiếm, do vậy chỉ áp dụng được cho những dãy đã có thứ tự.
Giải thuật tìm nhị phân tiết kiệm thời gian hơn rất nhiều so với giải thuật tìm tuần tự do
Tnhị phân (n) = O(log 2 n) < Ttuần tự (n) = O(n).
Cấu trúc Dữ liệu - Tìm kiếm và Sắp xếp
22
Tìm kiếm nhị phân
Nhận xét:
Khi muốn áp dụng giải thuật tìm nhị phân cần phải xét đến thời gian sắp xếp dãy số để thỏa điều kiện dãy số có thứ tự. Thời gian này không nhỏ, và khi dãy số biến động cần phải tiến hành sắp xếp lại => khuyết điểm chính cho giải thuật tìm nhị phân.
Cần cân nhắc nhu cầu thực tế để chọn một trong hai giải thuật tìm kiếm trên sao cho có lợi nhất.
Cấu trúc Dữ liệu - Tìm kiếm và Sắp xếp
23
Bài tập tổng hợp
Làm bài tập trong vở bài tập, kiểm tra vở vào buổi học kế tiếp
hãy nêu 1 ưu điểm và 1 khuyết điểm mà theo bạn là tiêu biểu nhất của từng phương pháp sắp xếp đã học.
Xét thuật toán tìm tuần tự một số nguyên X cho trước một mảng a gồm 1000 số nguyên. Trong trường hợp sau, hãy cho biết số phần tử tối đa có thể được duyệt trong quá trình tìm kiếm:
TH1: các phần tử của mảng a chưa được sắp xếp.
TH2: các phần tử của mảng a được sắp xếp tăng dần.
TH3: các phần tử của mảng a được sắp xếp giảm dần
Cấu trúc Dữ liệu - Tìm kiếm và Sắp xếp
24
Bài tập tổng hợp(tt)
Minh họa việc sắp xếp tăng dần dãy số sau bằng tất cả phương pháp đã học.(ghi rõ số so sánh, số phép hoán vị)
12 64 23 42 62 65 85 82 83 4
Sử dụng thuật toán tìm nhị phân để minh họa việc tìm kiếm số: 65, 70. (ghi rõ số phép so sánh, số phép gán)
Viết vào vở 1 lần các thuật toán sắp xếp đã học (sắp xếp giảm dần), có giải thích từng dòng.


Cấu trúc Dữ liệu - Tìm kiếm và Sắp xếp
25
Bài tập tổng hợp(tt)
TH trên máy, nộp vào đầu tuần sau:(hệ số 1)
Bt1: viết chương trình:
Định nghĩa một mảng gồm 10.000 phần tử kiểu int
Thực hiện 3 lần các thao tác sau:
Gán giá trị ngẫu nhiên (từ 0 ...10.000)lần lượt cho các phần tử mảng
Thực hiện việc sắp xếp theo thứ tự tăng dần bằng 5 phương pháp(in ra số lần hoán vị)
Tìm kiếm phần tử ngẫu nhiên(từ 0..10.000)(in ra số phép gán) bằng pp nhị phân




Cấu trúc Dữ liệu - Tìm kiếm và Sắp xếp
26
Bài tập tổng hợp(tt)
Bt2: viết chương trình:
Cho trước file dạng text có tên BANGDIEM.txt có nhiều dòng:
Dòng đầu tiên chứa số nguyên cho biến bao nhiêu sinh viên trong danh sách.
Mỗi dòng tiếp theo cho chứa họ tên và điểm 3 môn cơ bản(Toán, Lý, Hóa, TB) của mỗi sv, điểm là số thực:
Xây dựng cấu trúc (struct) để lưu tt mỗi sinh viên đó.
Đọc file để đưa vào một mảng gồm 100 phần tử, mỗi phần tử là 1 cấu trúc như trên.
Tính điểm trung bình của từng SV, và sắp xếp mảng giảm dần theo điểm trung bình, và ghi vào file BDSAPXEP.TXT.




Cấu trúc Dữ liệu - Tìm kiếm và Sắp xếp
27
Bài tập tổng hợp(tt)
BANGDIEM.TXT



BDSAPXEP.TXT
4
TranVanNam 5 7 9
NguyenVanThuan 8 6 10
PhamChiThanh 6 9 8
NguyenNgocAnh 3 6 7
4
NguyenVanThuan 8 6 10 8.0
PhamChiThanh 6 9 8 7.7
TranVanNam 5 7 9 7.0
NguyenNgocAnh 3 6 7 5.3