Thiết kế CSDL chương 5 (2009)

Chương V: SẮP XẾP VÀ TÌM KIẾM
1. Bài toán sắp xế�p
2. Một số phương pháp sắp xếp đơn giản
3. Sắp xếp nhanh
4. Sắp xếp hoà nhập (mergesort)
5. Bài toán tìm kiếm
6. Một số phương pháp tìm kiếm
1. BÀI TOÁN SẮP XẾP
Giả sử các đối tượng cần sắp xếp được biểu diễn bởi bản ghi gồm một số trường.
Một trong các trường đó được gọi là khoá sắp xếp. Kiểu của khoá là kiểu có thứ tự tuyến tính, được khai báo:
Type Object =record
Key : keytype;
[các trường khác]
end;
Var A : array[1..n] of object;
1. BÀI TOÁN SẮP XẾP
Bài toán : Cho mảng A[1..n] các đối tượng, ta cần sắp xếp lại các thành phần của mảng A để nhận được mảng A mới với các thành phần có các giá trị khoá tăng dần: A[1].key ? A[2].key ? ... ? A[n].key
2. Một số phương pháp sắp xếp đơn giản
2.1. Sắp xếp bằng lựa chọn(Selection Sort)
Tư tưởng:
Tìm phần tử có khoá nhỏ nhất trong mảng A[1..n]. Giả sử đó là A[k]. Trao đổi A[k] với A[1]. Và A[1] trở thành phần tử có khoá nhỏ nhất trong mảng.
Giả sử có A[1].key ? . ? A[i-1].key. Tìm phần tử có khoá nhỏ nhất trong mảng A[i ..n]. Giả sử đó là A[k], i ? k ?n. Lại trao đổi A[k] với A[i], ta nhận được A[1].key ? . ? A[i].key.
Lặp lại quá trình trên cho đến khi i=n-1, ta nhận được mảng A được sắp xếp.
Tư tưởng
Bước 1: i = 2; {giả sử có đoạn a[1] đã được sắp}
Bước 2: x = a[i]; Tìm vị trí j thích hợp từ a[1] đến a[i-1] để chèn a[i]
Bước 3: Dời các phần tử từ a[j] đến a[i-1] sang phải 1 vị trí
Bước 4: a[j] = x;
Bước 5: i = i+1; Nếu i  n : Lặp lại Bước 2.
Ngược lại : Dừng.
2.1. Sắp xếp bằng lựa chọn(Selection Sort)
Ví dụ. Xét mảng A[1..6] các số nguyên. Kết quả các bước sắp xếp được cho bởi bảng sau:
2.1. Sắp xếp bằng lựa chọn(Selection Sort)
Procedure selectionsort;
Var i, j, k: integer;
Begin
For i:=1 to n-1 do
Begin
k:=i;
for j:=i+1 to n do
if A[j].key< A[k].key then k:=j;
swap(A[i], A[k]);
End;
End;
2.2. Sắp xếp bằng xen vào (InsertionSort)
Tư tưởng:
Giả sử đoạn đầu của mảng A[1..i-1] (i ? 2) đã được sắp xếp. Xen A[i] vào vị trí thích hợp trong mảng A[1 ..i-1] để nhận được A[1 .. i] đã sắp xếp.
Lặp lại quá trình xen A[i] như thế với i chạy từ 2 đến n ta sẽ nhận được toàn bộ mảng A[1 .. n] được sắp.
4.2.2. Sắp xếp bằng xen vào (InsertionSort)
Procedure Insertionsort;
Var i, j : integer;
x : object;
ok : boolean;
Begin
For i:= 2 to n do
Begin
(2) j:=i-1; x:=A[i]; ok :=false;
(3) while j >=1 and not ok do
(4) if x.key < A[j].key then
Begin
A[j+1]:=A[j];
j:=j-1;
End;
Else ok :=true;
A[j+1] :=x;
End;
End;
Kết quả các bước sắp xếp xen vào
2.3. Sắp xếp nổi bọt (Bubblesort)
Tư tưởng:
Đi từ trái sang phải mảng, khi gặp hai phần tử kề nhau mà không đúng trật tự, thì ta trao đổi với nhau, như vậy ta sẽ có A[n] là phần tử có khóa lớn nhất trong mảng A[1..n].
Lặp lại với mảng A[1..n-1], ta sẽ nhận được A[n-1] là phần tử có khoá lớn nhất trong mảng A[1..n-1] và A[n-1].key ? A[n].key.
Lặp lại quá trình trên với mảng A[1..i], i chạy từ n giảm tới 2, ta sẽ nhận được mảng A[1..n] sắp xếp theo thứ tự khóa tăng dần.

Tư tưởng
Bước 1 : i = n;
Bước 2 : Cho j chạy từ 1 i-1 thực hiện
Nếu a[j].key > a[j+1].key: hoán vị a[j] với a[j+1];
Bước 3 : i = i-1;
Nếu i >= 2 : Lặp lại Bước 2.
Ngược lại: Dừng.
2.3. Sắp xếp nổi bọt (Bubblesort)
Procedure Bubblesort;
Var i, j : integer;
Begin
For i :=n downto 2 do
For j :=1 to i-1 do
if A[j].key > A[j+1].key then
swap(A[i], A[j+1]);
End;
Kết quả các bước sắp xếp nổi bọt
3. SẮP XẾP NHANH
Thiết kế dựa trên kĩ thuật chia-để-trị.
Đầu tiên, chọn một phần tử của mảng làm mốc.
Phân hoạch mảng thành hai phần: Phần bên phải có khoá lớn hơn mốc, phần bên trái có khoá nhỏ hơn hoặc bằng mốc.
Kết quả của phân hoạch, mốc đứng ở vị trí thứ k và phần trái mốc A[1..k-1] có khoá nhỏ hơn hoặc bằng khoá của mốc, phần phải mốc A[k+1 .. n] có khoá lớn hơn khoá của mốc.
Tiếp tục hai mảng con A[1 .. k-1] và A[k+1 ..n] được sắp xếp độc lập bằng cách gọi đệ quy thuật toán trên.
Thủ tục
Procedure QuickSort(i, j: integer);
Var k : integer;
Begin
If i < j then
Begin
Partition (i, j, k);
Quicksort(i, k-1);
Quicksort(k+1, j);
End;
End;
Thủ tục phân hoạch (Partition (i, j, k)).
Chọn phần tử đầu tiên của mảng làm mốc (p =A[i]).
Sử dụng hai biến, biến l chạy từ trái sang phải bắt đầu từ i, còn biến k chạy từ phải sang trái bắt đầu từ j+1.
Biến l được tăng cho tới khi A[l].key>p.key, còn biến k được giảm cho tới khi A[k]?p.key. Nếu lQuá trình trên được lặp lại cho đến khi l>k.
Cuối cùng trao đổi a[i] và a[k] để đặt mốc vào đúng vị trí.
Procedure Partition(i, j:integer; var k:integer);
Var l:integer;
P:object;
Begin
P:=A[i];
l:=i;
k:=j+1;
repeat l : = l+1 until (A[l].key > p.key) or (l>j);
repeat k : = k-1 until A[k].key<=p.key;
while l Begin
Swap(A[l], A[k]);
repeat l:=l+1 until A[l].key > p.key;
repeat k:=k-1 until A[k].key<=p.key;
End;
Swap(A[i], A[k]);
End;
4. SẮP XẾP HÒA NHẬP (MERGESORT)
Tư tưởng:
Thiết kế dựa trên kĩ thuật chia-để-trị.
Để sắp xếp mảng A[i..j] ta qui về sắp xếp hai mảng con A[1..k] và A[k+1..j] với k nằm giữa i và j, k = (i + j) div 2.
Sau đó hoà nhập hai mảng con đã được sắp xếp thành mảng được sắp xếp.
4. SẮP XẾP HÒA NHẬP (MERGESORT)
Procedure Megresort(i, j: integer);
Begin
If ( i < j) then
Begin
k:= (i+j) div 2;
Mergesort(i, k);
Mergesort(k+1, j);
Merge(i, k, j);
End;
End;
5. BÀI TOÁN TÌM KIẾM
Tìm kiếm các đối tượng dựa trên khoá tìm kiếm của chúng.
Có hai loại tìm kiếm: Tìm kiếm trong và tìm kiếm ngoài.
5. BÀI TOÁN TÌM KIẾM
Giả sử keytype là kiểu của khoá .
Các phần tử của danh sách có kiểu Item - bản ghi có chứa trường key kiểu keytype.
Type keytype = ... ;
Item = record
Key : keytype ;
[các trường khác]
End ;
List = record
Element : array [1 .. max] of Item ;
Count : 0 .. max ;
End ;
6. MỘT SỐ PHƯƠNG PHÁP TÌM KIẾM
Tìm kiếm tuần tự
Tìm kiếm nhị phân
Tìm kiếm tuần tự
Tư tưởng: Xuất phát từ đầu danh sách, chúng ta tuần tự đi trên danh sách cho tới khi tìm ra phần tử có khoá đã cho thì dừng lại, hoặc đi đến hết danh sách mà không tìm thấy.
Tìm kiếm tuần tự
Procedure SeqSearch (var L : List ; x : keytype;
Var found : boolean ; var p : 1 .. max) ;
Begin
Found : = false ;
P:= 1 ;
With L do
While (not found) and (p <= count) do
If element [p].key = x then found := true
Else p:= p+1 ;
End ;
Tìm kiếm nhị phân
Giả sử danh sách L được sắp xếp theo thứ tự khoá không giảm:
L.element [1].key L.element [2].Key ... L.element[n].key
Tư tưởng:
Đầu tiên ta so sánh khoá x với khoá của phần tử ở giữa danh sách, tức phần tử ở vị trí m = (1+n ) div 2:
Nếu x = L.element[m].key, ta đã tìm thấy.
Nếu x< L.element[m].key, ta tiếp tục tìm kiếm từ vị trí 1 đến vị trí m -1.
Nếu x > L.element[m].key, ta tiếp tục tìm kiếm từ vị trí m +1 đến vị trí n.
Nếu đến một thời điểm nào đó, ta phải tìm x trong một danh sách con rỗng, nghĩa là danh sách không chứa phần tử khoá x.
Thủ tục
Procedure BinarySearch(Var L: List ; x: keytype; Var found : boolean ; p : 1 .. max) ;
Var mid, bottom, top : integer ;
Begin
found := false;
bottom : = 1;
top := L.count;
While (not found) and (bottom <= top) do
Begin
mid := (bottom + top) div 2 ;
If x = L .element [mid].Key then found : = true
Else
If x < L .element [mid]. Key then top := mid -1
Else bottom := mid +1 ;
End ;
P:= mid ;
End ;