Sieu ho tro Homepage
Forum Home Forum Home > Information Technology > The programming language > Turbo Pascal,Turbo C
  New Posts New Posts RSS Feed - S? S?P X?P
  FAQ FAQ  Forum Search   Events   Register Register  Login Login


S? S?P X?P

 Post Reply Post Reply
Author
Message
Poster View Drop Down
Guest
Guest
Avatar

Joined: 23 January 2008
Status: Offline
Points: 378
Post Options Post Options   Thanks (0) Thanks(0)   Quote Poster Quote  Post ReplyReply Direct Link To This Post Topic: S? S?P X?P
    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 .
9
                                                1
                                     
                                    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?:
 
 2
                            
 9
 4
 
 
 

                            
 
 1
 5
 3
 
 

 3
 5
 1
 4
 2
 9
          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;                                            
 
Back to Top
Sponsored Links


Back to Top
Poster View Drop Down
Guest
Guest
Avatar

Joined: 23 January 2008
Status: Offline
Points: 378
Post Options Post Options   Thanks (0) Thanks(0)   Quote Poster Quote  Post ReplyReply Direct Link To This Post Posted: 21 August 2008 at 20:03
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, 75100,  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.
 
Back to Top
 Post Reply Post Reply
  Share Topic   

Forum Jump Forum Permissions View Drop Down

Forum Software by Web Wiz Forums® version 12.03
Copyright ©2001-2019 Web Wiz Ltd.

This page was generated in 0.063 seconds.
bao ky nam , Thuoc nam ky dieu
chu ky so