Môn CSDL: Tìm Kiếm - Sắp Xếp
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (63.57 KB, 4 trang )
CHƯƠNG 3:
TÌM KIẾM- SẮP XẾP
III.1. Tìm kiếm:
Trên thực tế tìm kiếm dữ liệu rất quan trọng trong đời sống khi muốn khai thác
một dữ liệu nào đó. Thường thì hệ thống thông tin lưu trữ lượng dữ liệu rất lớn nên
việc tìm kiếm nhanh rất có ý nghóa. Nếu hệ thống dữ liệu được tố chức theo trật tự
nào đó thì việc tìm kiếm sẽ nhanh và hiệu quả hơn.
Giải thuật tìm kiếm có hiệu quả còn phụ thuộc vào cấu trúc dữ liệu và bộ lưu trữ
nó. đây ta chỉ xét đơn giản dữ liệu được lưu trong bộ nhớ chính (tìm kiếm nội) và
dữ liệu được lưu trong mảng một chiều.
III.1.1. Tìm kiếm tuyến tính:
- Dãy số a
1
,a
2
, ,a
n
được lưu trong bộ nhớ chính: int a[n];
- Khóa cần tìm là x: int x;
a. Giải thuật: Ý chính của giải thuật là so sánh x lần lượt với từng phần tử trong
dãy a[n] cho tới khi tìm thấy giá trò a[i]=x, hoặc khi hết dãy.
Bước 1: i=0; //phần tử bắt đầu trong dãy a[n], theo ngôn ngữ C
Bước 2: So sánh a[i] với x:
- Nếu a[i]=x: Tìm thấy. Dừng.
- Nếu a[i]<>x: Sang bước 3.
Bước 3: i=i+1; //so sánh với phần tử kế tiếp trong dãy a
Nếu i>N: duyệt hết dãy và không tìm thấy. Thuật toán dừng.
Ngược lại: lặp lại bước 2.
b. Cài đặt:
int LinearSearch(int a[], int n, int x)
{
int i=0;
a[N]=x; //thêm phần tử (n+1) để kiểm soát x là luôn được tìm
thấy
(phần tử cầm canh)
while(a[i]!=x) i++; //vòng lặp dừng khi a[i]=x
if(i==N) return –1; //không tìm thấy x
else return i; //trả về vò trí thứ i của phần tử a[i]=x
}
c. Minh họa:
Dãy a: 12 2 8 5 1 6 4 15 . Tìm x=8:
i=0:
12 2 8 5 1 6 4 15
i=1:
12 2 8 5 1 6 4 15
i=2:
12 2 8 5 1 6 4 15
x=8
x=8
x=8
Dừng.
d. Đánh giá độ phức tạp:
- Dựa trên số lần so sánh giữa x và a[i].
Trường hợp Số lần so sánh Diễn giải
Tốt nhất 1 x là phần tử đầu tiên trong dãy
Xấu nhất n+1 x không có trong dãy
Trung bình
2
1+n
Tìm thầy giá trò a[i]=x với xác
suất như nhau cho mọi phần tử
trong dãy
- T(n)=O(n).
- Giải thuật tìm tuyến tính không phụ thuộc vào đặc tính của dãy. Đây là
phương pháp tổng quát nhất để tìm kiếm trên dãy số bất kỳ.
III.1.2. Tìm kiếm nhò phân:
Để hạn chế các bước so sánh, như khi dãy đã được sắp xếp (giả sử tăng dần) thì
khi tìm kiếm ta chỉ so sánh với phần tử giữa của dãy. Dựa vào kết quả so sánh này để
tiến hành so sánh hoặc nửa trên hoặc nửa dưới của dãy.
Nếu x > a
i
thì x có thể xuất hiện trong đoạn [a
i+1
a
n
].
Nếu x < ai thì x có thể xuất hiện trong đoạn [a
1
a
i-1
].
Ta phân đoạn dãy thành 2 dãy co trái và phải, so sánh x với phần tử giữa
a[(l+r)/2]. Nếu x>a[(l+r)/2] thì duyệt dãy (a[(l+r)/2+1], a[r]), ngược lại duyệt dãy
(a[l], a[(l+r)/2-1]). Nếu x=a[(l+r)/2], tìm thấy x. Nếu l>r, không tìm thấy x.
a. Giải thuật:
Bước 1: l=0; r=n-1;
Bước 2: m=(l+r)/2; //lấy phần tử giữa làm mốc so sánh
Có 3 khả năng:
- a[m]=x; //tìm thấy, dừng
- a[m]>x; //tìm tiếp x trong dãy a
l
a
m-1
r=m-1;
- a[m]<x; //tìm tiếp x trong dãy a
m-1
a
r
l=m+1;
Bước 3: Nếu l<=r //còn phần tử chưa xét, tìm tiếp
Lặp lại bước 2.
Ngược lại, dừng.
b. Cài đặt:
int BinarySearch(int a[], int n, int x)
{
int l=0, r=n-1, m;
do{
m=(l+r)/2;
if(x==a[m])
return m; //tìm thấy
else
if(x<a[m]) r=m-1;
else l=m+1;
}while(l<=r);
return –1;
}
c. Đánh giá độ phức tạp:
Trường hợp Số lần so sánh
Tốt nhất 1
Xấu nhất log
2
n
Trung bình log
2
n/2
- Độ phức tạp T(n)=O(log
2
n)
- Áp dụng cho dãy đã sắp xếp
- So với tìm tuyến tính thì tối ưu hơn
III.2. Sắp xếp:
III.2.1. Giới thiệu:
Sắp xếp là quá trình bố trí lại các phần tử của một tập đối tượng theo một thứ tự
được ấn đònh, chẳng hạn tăng dần hay giảm dần đối với một dãy số. Với một cấu trúc
đã được sắp xếp thì rất thuận tiện khi thực hiện các tác vụ như tìm kiếm, trích lọc,
duyệt cấu trúc,…
Có 2 loại giải thuật sắp xếp: Sắp xếp nội và Sắp xếp ngoại:
+ Sắp xếp nội:
Toàn bộ dữ liệu được đưa vào bộ nhớ trong
Kích thước dữ liệu cần sắp xếp không lớn lắm
Thời gian sắp sếp được thực hiện rất nhanh
+ Sắp xếp ngoại:
Chỉ một phần nhỏ dữ liệu cần sắp xếp được đưa vào bộ nhớ trong, phần lớn
dữ liệu còn lại được lưu ở bộ nhớ ngoài (đóa, băng từ,…)
Kích thước dữ liệu sắp xếp rất lớn
Thời gian sắp xếp chậm
Chúng ta chỉ quan tâm đến sắp xếp nội, dữ liệu là mảng (dãy) các số liệu cài đặt
theo mảng một chiều.
Các phương pháp sắp xếp nội:
1. Selection Sort
2. Insertion Sort
3. BInsertion Sort
4. Interchange Sort
5. Buble Sort
6. Shaker Sort
7. Shell Sort
8. Quick Sort
9. Heap Sort
10. Merge Sort
