S? S?P X?P |
Post Reply |
Author | |||||||||||||
Poster
Guest Joined: 23 January 2008 Status: Offline Points: 378 |
Post Options
Thanks(0)
Posted: 21 August 2008 at 20:02 |
||||||||||||
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?:
�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;
|
|||||||||||||
Sponsored Links | |||||||||||||
Poster
Guest Joined: 23 January 2008 Status: Offline Points: 378 |
Post Options
Thanks(0)
|
||||||||||||
3. Thu?t to�n s?p x?p ki?u Quicksort.
Trong c�c c�ch s?p x?p tru?c, � tu?ng co b?n l� ch?n ph?n t? nh? nh?t hay l?n nh?t c?a danh s�ch con n�o d� c?a danh s�ch d� cho, r?i d?t v�o d�ng v? tr� c?a n�.
B�y gi? ta x�t so d? s?p x?p kh�c g?i l� Quicksort n� cung ch?n m?t m?c v� d?nh v? m?c ?y, nhung kh�ng nh?t thi?t ph?i l� ph?n t? nh? nh?t hay l?n nh?t. Ta s? d?nh v? m?c n�y b?ng c�ch s?p x?p l?i danh s�ch con sao cho t?t c? c�c ph?n t? b�n tr�i l� nh? hon hay b?ng n�, c�n t? c? c�c ph?n t? b�n ph?i l?n hon n�. Nhu v?y danh s�ch ( con) du?c chia l�m hai danh s�ch con nh? hon ( ch�u) v� b?ng c�ch d� c�c danh s�ch con n�y l?i du?c s?p x?p m?t c�ch d?c l?p. Phuong ph�p �chia d? tr?� d?n d?n thu?t to�n s?p x?p d? quy.
So d? n�y s? ho?t d?ng t?t nh?t n?u n?u ph?n t? d?oc ch?n kh�ng l� ph?n t? bi�n m� l� m?t gi� tr? n�o d� ? gi?a danh s�ch.
V� d? ta x�t danh s�ch sau:
75, 70, 65, 84, 98, 78, 100, 93, 55, 61, 81, 68
�? don gi?n ta ch?n ph?n t? d?u ti�n l� 75 d? x�c d?nh d�ng v? tr� c?a n�, t?c l� c�c s? 70, 65, 55, 61v� 68 d?ng b�n tr�i 75 c�n 84, 98, 78, 100, 93 v� 81 ? b�n ph?i, th? t? c?a c�c danh s�ch con n�y ta kh�ng quan t�m.
Th?c hi?n hai l?n t�m ki?m, m?t l� t�m c�c s? nh? hon hay b?ng 75 t? b�n ph?i, v� sau d� l� t�m ph?n t? lon hon 75 t? b�n tr�i.
75, 70, 65, 84, 98, 78, 100, 93, 55, 61, 81, 68
Sau khi ho�n v? hai ph?n t? n�y ta l?i t�mm ph�n t? nho hon hay b?n 75 t? b�n ph?i v� ph?n t? l?n hon 75 t? b�n tr�i.
75, 70, 65, 68, 98, 78, 100, 93, 55, 61, 81, 84
C�c ph?n t? 61 v� 98 l?i du?c ho�n v?, c? ti?p t?c qu� tr�nh n�y ta dI d?n t�nh c?nh sau:
75, 70, 65, 68, 61, 55, 100, 93, 78, 98, 81, 84
Hai con tr? tr�i ph?i g?p nhau, b�o hi?u k?t th�c thu?t to�n. B�y gi? ta ch? vi?c ho�n v? 75 v?i 55 l� xong:
55, 70, 65, 68, 61, 75, 100, 93, 78, 98, 81, 84
�� ch�nh l� n?i dung c?a th? t?c SPLIT du?i d�y:
PROCEDURE SPLIT (Var X:MG;Low,High:Integer;Var Pos:Integer);
{Input: X mang co chi so dau la Low va chi so cuoi la High
OutPut: Pt dau duoc dat dung vi tri theo thu tu tai Pos }
Var
Item: ElementType;
Left,Right:Integer; {chi so trai, phai de tim vi tri cho Item }
Begin
Item:=X[Low]; { Chon Item la pt dau }
Left:=Low;
Right:=High;
While Left<Right do { hai chi so chua trung nhau }
Begin
While X[Right] >Item do
Right:=Right-1; { dung tai pt nho hon Item}
While (Left< Right) and (X[Left] <= Item) do
Left:=Left+1; { dung tai pt lon hon hay bang Item}
{ Hoan vi hai pt neu hai con tro chua gap nhau}
If Left< Right then Interchange(X[Left],X[Right]);
End; {of while}
Pos:=Right;
Interchange(X[Low],X[Pos]); {Dat pt dau vao Pos tim duoc}
End;
B�y gi? ta c� th? vi?t du?c th? t?c d? quy Quicksort nhu sau. N?u s? ph?n t? nh? hon hay b?ng 1 th� kh�ng c?n ph?i l�m g�. Ngu?c l?i d�ng SPLIT chia th�nh 2 danh s�ch con, v� sau d� l?i d�ng d? quy Quicksort cho 2 danh s�ch d�.
PROCEDURE QUICKSORT( Var X: MG; Low, High: Integer);
{ sap xep cac pt cua mang theo thu tu, bang de quy}
Var
Pos:Integer;
Begin
If (0<High-Low) then {danh sach nhieu hon mot muc}
Begin
Split(X,Low,High,Pos); {chia thanh 2 ds con}
QuicKSort(X,Low,Pos-1); {Sap xep danh sach con trai}
QuicKSort(X,Pos+1,High); {Sap xep danh sach con phai}
End;
End;
Chuong tr�nh d?y d? ?ng d?ng ki?u Quicksort v?i vi?c ch?n ph?n t? trung b�nh l� ph?n t? gi?a c?a 3 p?n t? Low , High v� Mid, v� d?i v?i danh s�ch �t hon 20 ph?n t? th� d�ng x?p ch�n, khi s? ph?n t? nhi?u hon m?i d�ng Quicksort d? tang th�m hi?u qu?.
PROGRAM QUICK_SORT;
Uses Crt;
CONST MAXSIZE=100;
Type
ElementType= Real;
MG = ARRAY[1..MAXSIZE] OF ElementType;
Var N,i: Integer;
DANHSACH:MG;
PROCEDURE Interchange (VAR A,B :ElementType);
VAR
Temp:ElementType;
Begin
Temp:=A;
A:=B;
B:=Temp;
End;
PROCEDURE DOC(Var X: MG);
{ Tao mang co gia tri thuc ngau nhien }
BEGIN
ClrScr;
Write('doc n = '); Readln(n);
FOR I:=1 TO n DO
X:=-10*Random+Random(n);
END;
PROCEDURE XEPCHEN( Var A: MG; m:Integer);
Var
ptchen: ElementType;
J,I:Integer;
Begin
for I:=2 to M do
Begin
ptchen:=a;
if (ptchen <a[i-1]) then {tim vi tri chen}
begin
J:=i-1;
while (ptchen <a[j]) and (j>=1) do
begin
a[j+1]:=a[j]; {dich sang phai tao cho trong}
J:=j-1;
end;
a[j+1]:=ptchen;
end;
End;
end;
FUNCTION MID_OF_THREE (A,B,C: ElementType):ElementType;
Var Y: MG;
Begin
Y[1]:=a;y[2]:=B;y[3]:=c;
xepchen(Y,3);
mid_of_three:=y[2];
End;
PROCEDURE SPLIT ( Var X:MG; Low,High:Integer;Var Pos:Integer);
{Input: X mang co chi so dau la Low va chi so cuoi la High
OutPut: Dat pt dau vao dung vi tri theo thu tu tai Pos }
Var
Item,tb: ElementType;
Mid,Left,Right:Integer; {chi so trai, phai de tim vi tri cho Item }
Begin
{ Chon Item la pt trung binh cua 3 pt Low,High va Mid de 2
danh sach con gan bang nhau, nang hieu qua Quicksort}
Mid:= (Low+High) div 2;
Item:= Mid_of_three (X[Low],X[Mid],X[High]);
Item:=X[Low]; { Dat Item la pt dau }
Left:=Low;
Right:=High;
While Left<Right do { hai chi so chua trung nhau }
Begin
While X[Right] >Item do
Right:=Right-1; { chi vao pt nho hon Item}
While (Left< Right) and (X[Left] <= Item) do
Left:=Left+1; { chi vao pt lon hon hay bang Item}
{ Hoan vi hai pt neu hai con tro chua gap nhau}
If Left< Right then Interchange(X[Left],X[Right]);
End; {of while}
Pos:=Right;
Interchange(X[Low],X[Pos]);
End; {Split}
PROCEDURE QUICKSORT( Var X:MG; Low,High:Integer);
{ sap xep cac pt cua mang theo thu tu, bang de quy}
Var
Pos:Integer;
Begin
If (0<High-Low) then {danh sach nhieu hon mot muc}
If (High-Low<20) then {danh sach nho hon 20 muc }
XEPCHEN(X,High-Low)
Else {danh sach lon dung Quicksort}
Begin
Split(X,Low,High,Pos); {chia thanh 2 ds con}
QuicKSort(X,Low,Pos-1); {Sap xep ds con trai}
QuicKSort(X,Pos+1,High); {Sap xep ds con phai}
End;
End; {QuickSort}
PROCEDURE HIEN( X:MG);
BEGIN
FOR I:=1 TO n DO
Write(X:6:2,' ');
Writeln;
END;
BEGIN
ClrScr;
DOC (danhsach);
HIEN(DANHSACH);
Quicksort(danhsach,1,n);
HIEN(DANHSACH);
Readln;
END.
N?u Quicksort du?c d�ng nhi?u n�n vi?t du?i d?ng l?p.
|
|||||||||||||
Post Reply | |
Tweet
|
Forum Jump | Forum Permissions You cannot post new topics in this forum You cannot reply to topics in this forum You cannot delete your posts in this forum You cannot edit your posts in this forum You cannot create polls in this forum You cannot vote in polls in this forum |