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 bi ton tm ki?m, bi ton s?p x?p m?t nhm cc m?c d? li?u cung r?t quan tr?ng. Hai v?n d? ny lin quan v?i nhau, c th? dng m?t s? thu?t ton c hi?u qu? ch? khi d? li?u du?c t? ch?c trong m?t danh sch c th? t?. Trong ph?n ny chng ta s? xt bi ton s?p x?p th? t? m?t danh sch:
                             X1,X2,...,Xn
theo m?t tru?ng kho no d.
 
1. M?t vi so d? s?p x?p v?i d? ph?c t?p O(n2).
          C 3 phuong php s?p x?p don gi?n thng 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 chn (insertion sort).
  C? 3 d?u r?t don gi?n, nhung ki?u th? ba du?c ua dng hon, nh?t l v?i danh sch nh?.
 
a) S?p x?p b?ng l?a ch?n don gi?n.
          So d s?p x?p ki?u ny l di qua nhi?u l?n danh sch 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 dng v? tr mong mu?n.
1) THU?T TON S?P X?P KI?U L?A CH?N ON GI?N CHO
CC DANH SCH U?C CI ?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 cc danh sch lin k?t ta cung lm nhu v?y ch? c?n thay cc ch? s? i, j b?ng cc con tr? ch?y trong danh sch v danh sch 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 sch 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 sch con}
                   SmallPtr^.Data:=P^.Data;
                   P^.Data:=Smallest;
                   P:=P^.Next;
               End;
     END;
         
          L?n d?u tin di qua danh sch, d? tm ph?n t? nh? nh?t ta ph?i th?c hi?n n php so snh, 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 snh, nghia l d? ph?c t?p c?a cch s?p x?p ny l O(n2) trong m?i tru?ng h?p.
 
b) S?p x?p ki?u n?i b?t.
          Cch s?p x?p ny cung di qua nhi?u l?n danh sch v cc danh sch con. M?i l?n di qua t?ng c?p ph?n t? du?c so snh v s?p l?i (hon v?) cho dng th? t?. Sau l?n duy?t qua danh sch d?u tin, ph?n t? nh? nh?t n?i ln trn, t.l ? v? tr cu?i danh sch. Qu trnh d l?p l?i d?i v?i danh sch con l danh sch c?a bu?c tru?c b? di ph?n t? cu?i cng. K?t thc chuong trnh khi d?t t?i danh sch con c ch? m?t ph?n t?. Ta c th? dng thu?t ton l?p kp 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 cch s?p n?i b?t l khi danh sch c th? t? ngu?c l?i. L?n d?u th?c hi?n n-1 php so snh v hon 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 snh, hay d? ph?c t?p c?a thu?t ton l O(n2).
 
b) S?p x?p ki?u chn.
          Thu?t ton s?p ki?u chn du?c xy d?ng trn co s? chn ph?n t? m?i vo m?t danh sch d du?c s?p th? t? d? nh?n du?c danh sch m?i cung c th? t? dng. Phuong php ny tuong t? nhu khi m?t ngu?i choi t-lo-kho, m?i l?n nh?n du?c con bi du?c chia, anh ta chn dng theo th? t? d?nh tru?cvo cc con bi d ? trn tay anh ta (khng tnh d?n mu v ch?t).
          Thu?t ton du?i dy m t? th? t?c chn ny vo danh sch du?c luu tr? trong m?ng. Trong giai do?n th? i, ph?n t? Xi du?c chn vo dng v? tr c?a n trong danh sch cc ph?n t? X1,X2,..,Xi-1 d du?c s?p th? t?. Ta th?c hi?n di?u ny b?ng cch so snh Xi v?i cc ph?n t? ny b?t d?u t? bn ph?i v d?ch sang bn tri khi c?n thi?t. V? tr 0 c?a m?ng du?c gi? s? nh?n gi tr? cm no d (k hi?u l - ) nh? hon m?i ph?n t? c?a danh sch d? trnh roi sang bn tri kh?i danh sch.
 
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 sch c th? t? ngu?c l?i. Chn X[2] c?n 2 l?n so snh (v?i  X[1] v X[0] ), chn X[3] c?n 3 l?n,...T?ng s? l:
                  
v?y th?i gian tnh l O(n2).
          C th? p d?ng cch s?p x?p ki?u chn cho cc danh sch lin k?t.
          Ni chung c? 3 ki?u s?p x?p trn d?u khng t?t l?m v khng c g kh?ng d?nh thu?t ton no du?c uu tin hon. Tuy nhin do s? l?n hon v? t m s?p x?p ki?u chn du?c ua chu?ng hon cch l?a ch?n v cch n?i b?t, nh?t l d?i v?i danh sch nh? (c ch?ng 15 - 20 ph?n t?) v cc danh sch d du?c s?p m?t ph?n.
 
2. Kh?i (Heap) v HeapSort.
          Ba ki?u s?p x?p trn d?u c d? ph?c t?p l O(n2) trong tru?ng h?p t?i v tru?ng h?p trung bnh. Cn c cc thu?t ton khc v?i d? ph?c t?p l O(n.log2 n), t.l hi?u qu? hon cc thu?t ton trn trong da s? tru?ng h?p. Ta s? m t? m?t thu?t ton nhu th?, g?i l HeapSort, n l bi?n th?c c?a ki?u ch?n don gi?n. ? dng du?c thu?t ton ny c?n ph?i t? ch?c l?i d? li?u theo m?t c?u trc g?i l kh?i (Heap).
         
a)?nh nghia kh?i (Heap) .
          Cung nhu cy tm ki?m nh? phn (BST), kh?i l lo?i cy nh? phn d?c bi?t. N khc v?i BST ? hai di?m:
          1. N l d?y d?, nghia l cc l n?m nhi?u nh?t ? hai m?c lin ti?p nhau, v cc l ? m?c th?p n?m ? v? tr bn tri nh?t.
          2. Gi tr? c?a m?c d? li?u ? nt b? l?n hon gi tr? c?a m?c tuong ?ng ? cc nt con c?a n.
 
          ? ci d?t kh?i ta c th? dng c?u trc lin k?t gi?ng nhu BST, nhung thu?ng ngu?i ta dng m?ng d? vi?c tm ki?m c hi?u qu? hon. Ta dnh s? cc nt trong kh?i  t? trn ( g?c) xu?ng du?i, ? m?i m?c cc nt du?c dnh s? t? tri qua ph?i. D? li?u ? nt th? i du?c luu tr? t?i v? tr th? i c?a m?ng. Tnh d?y d? c?a Kh?i d?m b?o cc m?c d? li?u du?c luu tr? trong cc v? tr lin 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 bo nhu sau:
 
          CONST      
                   HeapLimit = . . . {gi?i h?n s? nt trong kh?i}
          TYPE
                   ElementType= . . , {Ki?u c?a m?c d? li?u }
                   HeapType=ARRAY[1.. HeapLimit] OF ElementType;
          VAR
                   Heap: HeapType;
 
          Cc m?c trong kh?i ? trn 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 cch ci d?t nhu v?y, cc nt con c?a nt i s? n?m ? v? tr th? 2i v 2i+1, v nt b? c?a nt 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 tin ta ci d?t n ph?n t? ny thnh cy nh? phn d?y d?. N?u c m?t thu?t ton chuy?n cy ny thnh kh?i th khi d ph?n t? l?n nh?t s? n?m ? g?c c?a cy, t?c l ph?n t? d?u tin c?a m?ng. ?i ch? ph?n t? ny cho ph?n t? cu?i cng. Ti?p theo ta l?i p d?ng thu?t ton ny cho cy con g?m (n-1) ph?n t? d?u tin. Ph?n t? l?n nh?t l?i d? ? v? tr ( n-1) c?a m?ng. Qa trnh ny ti?p t?c d?n khi cy con ch? c 2 nt, ta ch? c?n hon v? l nh?n du?c danh sch theo th? t? tang d?n.
 
b) Thu?t ton hon-v?-xu?ng (SwapDown).
          Tru?c tin ta xt thu?t ton chuy?n cy nh? phn d?y d? thnh kh?i trong tru?ng h?p gi?n don nh?t, khi cy d g?n nhu l kh?i, t.l c? hai cy con t? nt g?c d l cc kh?i ( nhung b?n thn cy chua l kh?i). V d?:
 
 2
                            
 9
 4
 
 
 

                            
 
 1
 5
 3
 
 

 3
 5
 1
 4
 2
 9
          Cy ny d?y d? v c? hai cy con l cc kh?i , l do d? n khng l kh?i v gi tr? c?a m?c g?c l?i nh? hon ? m?t trong nt con c?a n. Bu?c d?u tin ta hon v? m?c ? g?c v?i nt con l?n hon,  ? dy l nt con tri.
 
 
 
 
 
 
 
 
 
 
 
          i?u ny d?m b?o cho m?c ? g?c l?n hon c? hai nt con, v m?t trong hai cy con, tru?ng h?p ny l cy ph?i, v?n l kh?i. Cy con kia c th? l kh?i v cung c th? l khng. N?u n cung l kh?i thu?t ton ch?m d?t. N?u n khng l kh?i th cc cy con c?a n cung l kh?i, t.l c th? p d?ng thu?t ton hon-v?-xu?ng cho cy con ny. Qu trnh ny l?p l?i chi t?i khi c? hai cy con ? nt dang xt l kh?i, ho?c t?i cy ch? c l. N?u cy ny chua l kh?i ta ch? c?n hon v? g?c v?i l l?n l xong. Thu?t ton k?t thc.
         
Thu?t ton trn du?c ci 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 ton Heapify.
          i v?i bi ton t?ng qut chuy?n cy nh? phn d?y d? thnh kh?i, ta b?t d?u t? nt cu?i cng khng ph?i l l ( nt c v? tr l n div 2), dng thu?t ton SwapDown d? chuy?n cy con ny thnh kh?i. Ti?p theo chuy?n ln nt tru?c d v l?i p d?ng SwapDown, ..Cu?i cng ta d?t t?i nt g?c c?a cy. Thu?t ton chuy?n cy 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 ton Heapsort.
          ? s?p x?p cc ph?n t? trong m?ng X theo th? t? tang d?n du?c ti?n hnh nhu sau:
          1. xem X nhu cy nh? phn v dng Heapify d? chuy?n n thnh kh?i.
          2. FOR I= n div 2 TO 2  lm cc vi?c sau;
                   a. Hon v? X[1] v X d? dua ph?n t? l?n nh?t trong danh sch
                              con d?n cu?i c?a danh sch ?y.
                   b. Dng thu?t ton SwapDown d? chuy?n cy nh? phn t? nt 1
                              t?i nt i-1 thnh 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 ton s?p x?p ki?u Quicksort.
          Trong cc cch 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 sch con no d c?a danh sch d cho, r?i d?t vo dng v? tr c?a n.
          By gi? ta xt so d? s?p x?p khc g?i l Quicksort n cung ch?n m?t m?c v d?nh v? m?c ?y, nhung khng 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 ny b?ng cch s?p x?p l?i danh sch con sao cho t?t c? cc ph?n t?  bn tri l nh? hon hay b?ng n, cn t? c? cc ph?n t? bn ph?i l?n hon n. Nhu v?y danh sch ( con) du?c chia lm hai danh sch con nh? hon ( chu) v b?ng cch d cc danh sch con ny l?i du?c s?p x?p m?t cch d?c l?p.  Phuong php chia d? tr?  d?n d?n thu?t ton s?p x?p d? quy.
          So d? ny s? ho?t d?ng t?t nh?t n?u n?u ph?n t? d?oc ch?n khng l ph?n t? bin m l m?t gi tr? no d ? gi?a danh sch.
          V d? ta xt danh sch sau:
                   75, 70, 65, 84, 98, 78, 100, 93, 55, 61, 81, 68
           ? don gi?n ta ch?n ph?n t? d?u tin l 75 d? xc d?nh dng v? tr c?a n, t?c l cc s? 70, 65, 55, 61v 68 d?ng bn tri 75 cn 84, 98, 78, 100, 93 v 81 ? bn ph?i, th? t? c?a cc danh sch con ny ta khng quan tm.
          Th?c hi?n hai l?n tm ki?m, m?t l tm cc s? nh? hon hay b?ng 75 t? bn ph?i, v sau d l tm ph?n t? lon hon 75 t? bn tri.
                  
          75,  70,  65,  84,  98,  78,  100,  93,  55,  61,  81,  68
 

          Sau khi hon v? hai ph?n t? ny ta l?i tmm phn t? nho hon hay b?n 75 t? bn ph?i v ph?n t? l?n hon 75 t? bn tri.
 

          75,  70,  65,  68,  98,  78,  100,  93,  55,  61,  81,  84
 

          Cc ph?n t? 61 v 98 l?i du?c hon v?, c? ti?p t?c qu trnh ny ta dI d?n tnh c?nh sau:
 

          75,  70,  65,  68,  61, 55,  100,  93,  78,  98,   81,  84
 
 

Hai con tr? tri ph?i g?p nhau, bo hi?u k?t thc thu?t ton. By gi? ta ch? vi?c hon v? 75 v?i 55 l xong:
 
          55,  70,  65,  68,  61, 75100,  93,  78,  98,   81,  84
 
          chnh l n?i dung c?a th? t?c SPLIT du?i dy:
 
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;
 
          By 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 khng c?n ph?i lm g. Ngu?c l?i dng SPLIT chia thnh 2 danh sch con, v sau d l?i dng d? quy Quicksort cho 2 danh sch 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 trnh d?y d? ?ng d?ng ki?u Quicksort v?i vi?c ch?n ph?n t? trung bnh l ph?n t? gi?a c?a 3 p?n t? Low , High v Mid, v d?i v?i danh sch t hon 20 ph?n t? th dng x?p chn, khi s? ph?n t? nhi?u hon m?i dng Quicksort d? tang thm 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 dng nhi?u nn 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.203 seconds.
bao ky nam , Thuoc nam ky dieu
C?a thp ch?ng chy,cua thep chong chay,c?a ch?ng chy,cua chong chay,c?a nh?a abs,cua nhua abs,c?a abs,cua abs,cua thep van go,c?a thp vn g?,c?a thp an ton,cua thep an toan,c?a cu?n ch?ng chy,cua cuon chong chay,c?a g? ch?ng chy,cua go chong chay,c?a tru?t t? d?ng,cua truot tu dong,c?a knh ch?ng chy,cua kinh chong chay