S? S?P X?P.
(Sorting)
Cung nhu b�i to�n t�m ki?m, b�i to�n s?p x?p m?t nh�m c�c m?c d? li?u cung r?t quan tr?ng. Hai v?n d? n�y li�n quan v?i nhau, c� th? d�ng m?t s? thu?t to�n c� hi?u qu? ch? khi d? li?u du?c t? ch?c trong m?t danh s�ch c� th? t?. Trong ph?n n�y ch�ng ta s? x�t b�i to�n s?p x?p th? t? m?t danh s�ch:
X1,X2,...,Xn
theo m?t tru?ng kho� n�o d�.
1. M?t v�i so d? s?p x?p v?i d? ph?c t?p O(n2).
C� 3 phuong ph�p s?p x?p don gi?n th�ng d?ng:
- l?a ch?n don gi?n (simple selection sort),
- s?p x?p n?i b?t (buble sort)
- s?p x?p ki?u ch�n (insertion sort).
C? 3 d?u r?t don gi?n, nhung ki?u th? ba du?c ua d�ng hon, nh?t l� v?i danh s�ch nh?.
a) S?p x?p b?ng l?a ch?n don gi?n.
So d� s?p x?p ki?u n�y l� di qua nhi?u l?n danh s�ch hay m?t ph?n c?a n�, v� m?i l?n di qua c� m?t ph?n t? du?c s?p x?p theo d�ng v? tr� mong mu?n.
1) THU?T TO�N S?P X?P KI?U L?A CH?N �ON GI?N CHO
C�C DANH S�CH �U?C C�I �?T B?NG M?NG.
PROCEDURE SAP_CHON_A ( Var A:mg; m:Integer);
Var SmallPos,Smallest: Integer;
BEGIN
FOR I:=1 TO M-1 DO
Begin
SmallPos:=i;
Smallest:=A[SmallPos];
For j:=i+1 to m DO
If (A[j] <Smallest) then
Smallest:=A[j];
A[SmallPos]:=Smallest;
End;
END;
�?i v?i c�c danh s�ch li�n k?t ta cung l�m nhu v?y ch? c?n thay c�c ch? s? i, j b?ng c�c con tr? ch?y trong danh s�ch v� danh s�ch con.
PROCEDURE SAP_CHON_P( Var List:PointerType);
Var
Smallest:ElementType;
P,Q,SmallPtr: PointerType;
BEGIN
P:=List;
While P<> NIl do
Begin {Ch?n ph?n t? nh? nh?t trong danh s�ch con Xi toi Xn}
SmallPtr:=P;
Smallest:=SmallPtr^.Data;
Q:=P^.Next;
WHILE Q<>nil DO
Begin
If (Q^.Data <Smallest) then
Begin
SmallPtr:=Q;
Smallest:=Q^.Data;
End;
Q:=Q^.Next;
End;
{ Chuy?n ph?n t? nh? nh?t d?n d?u danh s�ch con}
SmallPtr^.Data:=P^.Data;
P^.Data:=Smallest;
P:=P^.Next;
End;
END;
L?n d?u ti�n di qua danh s�ch, d? t�m ph?n t? nh? nh?t ta ph?i th?c hi?n n ph�p so s�nh, l?n th? hai l� n-1,...Nhu v?y t?t c? l�:
(n-1) + (n-2)+... +2+1 = n(n-1)/2
l?n so s�nh, nghia l� d? ph?c t?p c?a c�ch s?p x?p n�y l� O(n2) trong m?i tru?ng h?p.
b) S?p x?p ki?u n?i b?t.
C�ch s?p x?p n�y cung di qua nhi?u l?n danh s�ch v� c�c danh s�ch con. M?i l?n di qua t?ng c?p ph?n t? du?c so s�nh v� s?p l?i (ho�n v?) cho d�ng th? t?. Sau l?n duy?t qua danh s�ch d?u ti�n, ph?n t? �nh? nh?t� n?i l�n tr�n, t.l ? v? tr� cu?i danh s�ch. Qu� tr�nh d� l?p l?i d?i v?i danh s�ch con l� danh s�ch c?a bu?c tru?c b? di ph?n t? cu?i c�ng. K?t th�c chuong tr�nh khi d?t t?i danh s�ch con c� ch? m?t ph?n t?. Ta c� th? d�ng thu?t to�n l?p k�p hay d? quy nhe sau:
PROCEDURE SAP_NOI_BOT( Var A:mg; m:Integer);
Var tg:integer;
begin
if m>1 then
begin
For I:=1 to m-1 do
If A > A[i+1] then {�?i ch? }
Begin
TG:=A; A:=A[i+1]; A[i+1]:=TG;
End;
Sap_noi_Bot(A,m-1);
end;
end;
Tru?ng h?p t?i nh?t trong c�ch s?p n?i b?t l� khi danh s�ch c� th? t? ngu?c l?i. L?n d?u th?c hi?n n-1 ph�p so s�nh v� ho�n v?, l?n 2 l� n-2,...V� v?y t?ng c?ng c�:
(n-1) + (n-2)+... +2+1 = n(n-1)/2
l?n so s�nh, hay d? ph?c t?p c?a thu?t to�n l� O(n2).
b) S?p x?p ki?u ch�n.
Thu?t to�n s?p ki?u ch�n du?c x�y d?ng tr�n co s? ch�n ph?n t? m?i v�o m?t danh s�ch d� du?c s?p th? t? d? nh?n du?c danh s�ch m?i cung c� th? t? d�ng. Phuong ph�p n�y tuong t? nhu khi m?t ngu?i choi t�-lo-kho, m?i l?n nh?n du?c con b�i du?c chia, anh ta ch�n d�ng theo th? t? d?nh tru?cv�o c�c con b�i d� ? tr�n tay anh ta (kh�ng t�nh d?n m�u v� ch?t).
Thu?t to�n du?i d�y m� t? th? t?c ch�n n�y v�o danh s�ch du?c luu tr? trong m?ng. Trong giai do?n th? i, ph?n t? Xi du?c ch�n v�o d�ng v? tr� c?a n� trong danh s�ch c�c ph?n t? X1,X2,..,Xi-1 d� du?c s?p th? t?. Ta th?c hi?n di?u n�y b?ng c�ch so s�nh Xi v?i c�c ph?n t? n�y b?t d?u t? b�n ph?i v� d?ch sang b�n tr�i khi c?n thi?t. V? tr� 0 c?a m?ng du?c gi? s? nh?n gi� tr? c�m n�o d� (k� hi?u l� -� ) nh? hon m?i ph?n t? c?a danh s�ch d? tr�nh � roi sang b�n tr�i � kh?i danh s�ch.
PROCEDURE XEPCHEN( Var A:mg; m:Integer);
Begin
for i:=2 to M do
Begin
ptchen:=A;
if (ptchen <A[i-1]) then
Begin
j:=i-1;
While (ptchen < A[j]) Do
begin
a[j+1]:=a[j];
J:=j-1;
end;
A[j+1]:=ptchen;
End;
End;
End;
Tru?ng h?p t?i t? nh?t l� khi danh s�ch c� th? t? ngu?c l?i. Ch�n X[2] c?n 2 l?n so s�nh (v?i X[1] v� X[0] ), ch�n X[3] c?n 3 l?n,...T?ng s? l�:
v?y th?i gian t�nh l� O(n2).
C� th? �p d?ng c�ch s?p x?p ki?u ch�n cho c�c danh s�ch li�n k?t.
N�i chung c? 3 ki?u s?p x?p tr�n d?u kh�ng t?t l?m v� kh�ng c� g� kh?ng d?nh thu?t to�n n�o du?c uu ti�n hon. Tuy nhi�n do s? l?n ho�n v? �t m� s?p x?p ki?u ch�n du?c ua chu?ng hon c�ch l?a ch?n v� c�ch n?i b?t, nh?t l� d?i v?i danh s�ch nh? (c� ch?ng 15 - 20 ph?n t?) v� c�c danh s�ch d� du?c s?p m?t ph?n.
2. Kh?i (Heap) v� HeapSort.
Ba ki?u s?p x?p tr�n d?u c� d? ph?c t?p l� O(n2) trong tru?ng h?p t?i v� tru?ng h?p trung b�nh. C�n c� c�c thu?t to�n kh�c v?i d? ph?c t?p l� O(n.log2 n), t.l hi?u qu? hon c�c thu?t to�n tr�n trong da s? tru?ng h?p. Ta s? m� t? m?t thu?t to�n nhu th?, g?i l� HeapSort, n� l� bi?n th?c c?a ki?u ch?n don gi?n. �? d�ng du?c thu?t to�n n�y c?n ph?i t? ch?c l?i d? li?u theo m?t c?u tr�c g?i l� kh?i (Heap).
a)�?nh nghia kh?i (Heap) .
Cung nhu c�y t�m ki?m nh? ph�n (BST), kh?i l� lo?i c�y nh? ph�n d?c bi?t. N� kh�c v?i BST ? hai di?m:
1. N� l� d?y d?, nghia l� c�c l� n?m nhi?u nh?t ? hai m?c li�n ti?p nhau, v� c�c l� ? m?c th?p n?m ? v? tr� b�n tr�i nh?t.
2. Gi� tr? c?a m?c d? li?u ? n�t b? l?n hon gi� tr? c?a m?c tuong ?ng ? c�c n�t con c?a n�.
�? c�i d?t kh?i ta c� th? d�ng c?u tr�c li�n k?t gi?ng nhu BST, nhung thu?ng ngu?i ta d�ng m?ng d? vi?c t�m ki?m c� hi?u qu? hon. Ta d�nh s? c�c n�t trong kh?i t? tr�n ( g?c) xu?ng du?i, ? m?i m?c c�c n�t du?c d�nh s? t? tr�i qua ph?i. D? li?u ? n�t th? i du?c luu tr? t?i v? tr� th? i c?a m?ng. T�nh d?y d? c?a Kh?i d?m b?o c�c m?c d? li?u du?c luu tr? trong c�c v? tr� li�n ti?p ? d?u m?ng .
2 3
4 5 6 7
M?t m?ng Heap nhu th? c� th? du?c khai b�o nhu sau:
CONST
HeapLimit = . . . {gi?i h?n s? n�t trong kh?i}
TYPE
ElementType= . . , {Ki?u c?a m?c d? li?u }
HeapType=ARRAY[1.. HeapLimit] OF ElementType;
VAR
Heap: HeapType;
C�c m?c trong kh?i ? tr�n du?c luu tr? nhu sau:
Heap[1]=9, Heap[2]=8, Heap[3]=4,
Heap[4]=6, Heap[5]=2, Heap[6]=3;
Ch� �. B?ng c�ch c�i d?t nhu v?y, c�c n�t con c?a n�t i s? n?m ? v? tr� th? 2i v� 2i+1, v� n�t b? c?a n�t j s? l� n?m ? v? tr� ( j div 2).
G?a s? ta c?n s?p x?p n ph?n t? theo th? t? tang d?n (gi?m d?n). Tru?c ti�n ta c�i d?t n ph?n t? n�y th�nh c�y nh? ph�n d?y d?. N?u c� m?t thu?t to�n chuy?n c�y n�y th�nh kh?i th� khi d� ph?n t? l?n nh?t s? n?m ? g?c c?a c�y, t?c l� ph?n t? d?u ti�n c?a m?ng. �?i ch? ph?n t? n�y cho ph?n t? cu?i c�ng. Ti?p theo ta l?i �p d?ng thu?t to�n n�y cho c�y con g?m (n-1) ph?n t? d?u ti�n. Ph?n t? l?n nh?t l?i d? ? v? tr� ( n-1) c?a m?ng. Q�a tr�nh n�y ti?p t?c d?n khi c�y con ch? c� 2 n�t, ta ch? c?n ho�n v? l� nh?n du?c danh s�ch theo th? t? tang d?n.
b) Thu?t to�n ho�n-v?-xu?ng (SwapDown).
Tru?c ti�n ta x�t thu?t to�n chuy?n c�y nh? ph�n d?y d? th�nh kh?i trong tru?ng h?p gi?n don nh?t, khi c�y d� g?n nhu l� kh?i, t.l c? hai c�y con t? n�t g?c d� l� c�c kh?i ( nhung b?n th�n c�y chua l� kh?i). V� d?:
C�y n�y d?y d? v� c? hai c�y con l� c�c kh?i , l� do d? n� kh�ng l� kh?i v� gi� tr? c?a m?c g?c l?i nh? hon ? m?t trong n�t con c?a n�. Bu?c d?u ti�n ta ho�n v? m?c ? g?c v?i n�t con l?n hon, ? d�y l� n�t con tr�i.
�i?u n�y d?m b?o cho m?c ? g?c l?n hon c? hai n�t con, v� m?t trong hai c�y con, tru?ng h?p n�y l� c�y ph?i, v?n l� kh?i. C�y con kia c� th? l� kh?i v� cung c� th? l� kh�ng. N?u n� cung l� kh?i thu?t to�n ch?m d?t. N?u n� kh�ng l� kh?i th� c�c c�y con c?a n� cung l� kh?i, t.l c� th? �p d?ng thu?t to�n ho�n-v?-xu?ng cho c�y con n�y. Qu� tr�nh n�y l?p l?i chi t?i khi c? hai c�y con ? n�t dang x�t l� kh?i, ho?c t?i c�y ch? c� l�. N?u c�y n�y chua l� kh?i ta ch? c?n ho�n v? g?c v?i l� l?n l� xong. Thu?t to�n k?t th�c.
Thu?t to�n tr�n du?c c�i d?t nhu sau:
PROCEDURE SwapDown(VAR Heap: HeapType;r,n:Integer);
{Input: Heap la cay con day du voi cac nut tu r toi n, trong do r la nut
goc. Cac cay con ben phai va ben trai cua no da tao thanh khoi.
OutPut: Heap thanh KHOI, t.l co phan tu o nut r lon nhat }
VAr
Child:Integer;
Done:Boolean;
PROCEDURE Interchange (VAR A,B :ElementType);
VAR
Temp:ElementType;
Begin
Temp:=A;
A:=B;
B:=Temp;
End;
BEGIN { cua SwapDown}
Done:=False;
Child:=2*r;
WHILE (NOT DONE) and (Child<=n) DO
Begin
{ Tim con lon nhat }
IF Child <n then
IF (Heap[Child] < Heap[Child+1] ) then Child:=Child+1;
{ Hoan vi nut con lon nhat neu can roi chuyen xuong cay con tiep theo}
IF Heap[r]<Heap[Child] THEN
Begin
Interchange(Heap[r],Heap[Child]);
r:=Child;
Child:=2*r;
End
ELSE
Done:=True;
End; { of While}
END;
c) Thu?t to�n Heapify.
��i v?i b�i to�n t?ng qu�t chuy?n c�y nh? ph�n d?y d? th�nh kh?i, ta b?t d?u t? n�t cu?i c�ng kh�ng ph?i l� l� ( n�t c� v? tr� l� n div 2), d�ng thu?t to�n SwapDown d? chuy?n c�y con n�y th�nh kh?i. Ti?p theo chuy?n l�n n�t tru?c d� v� l?i �p d?ng SwapDown, ..Cu?i c�ng ta d?t t?i n�t g?c c?a c�y. Thu?t to�n chuy?n c�y d?y d? sang kh?i nhu sau:
PROCEDURE Heapify(VAR Heap: HeapType; n:Integer);
{ Chuyen cay nhi phan day du luu o vi tri 1..n cua bang Heap
thanh khoi, tuc la co phan tu dau tien la lon nhat.}
Var
r:Integer;
Begin
FOR r:= (n div 2) DOWNTO 1 DO {Bat dau tu nut cuoi khong la la}
SwapDown (Heap,r,n);
End;
d) Thu?t to�n Heapsort.
�? s?p x?p c�c ph?n t? trong m?ng X theo th? t? tang d?n du?c ti?n h�nh nhu sau:
1. xem X nhu c�y nh? ph�n v� d�ng Heapify d? chuy?n n� th�nh kh?i.
2. FOR I= n div 2 TO 2 l�m c�c vi?c sau;
a. Ho�n v? X[1] v� X d? dua ph?n t? l?n nh?t trong danh s�ch
con d?n cu?i c?a danh s�ch ?y.
b. D�ng thu?t to�n SwapDown d? chuy?n c�y nh? ph�n t? n�t 1
t?i n�t i-1 th�nh kh?i.
PROCEDURE HeapSort (VAR X: HeapType; n:Integer);
{ S?p x?p m?ng X g?m n ph?n t? theo th? t? tang d?n}
VAR
I:Integer;
BEGIN
Heapify(x,n);
FOR I:=n DOWNTO 2 DO
Begin
Interchange(X[1],X);
SwapDown(X,1,i-1); {Bien cay con tu nut 1 toi i-1 thanh khoi}
End;
END;
|