Sắp xếp trong Pascal (tiếp theo)

Thứ năm - 06/08/2020 09:35
Nội dung của phương pháp này là chia dãy cần sắp thành các dãy con đã có thứ tự (gọi là các Run) và có số phần tử là lũy thừa của 2, sau đó tìm cách trộn dần chúng với nhau thành các Run có thứ tự có chiều dài tăng dần cho đến khi chỉ còn một Run thì quá trình sắp xếp kết thúc.
f) Phương pháp trộn (Merging sort)
* Giải thích:
Nội dung của phương pháp này là chia dãy cần sắp thành các dãy con đã có thứ tự (gọi là các Run) và có số phần tử là lũy thừa của 2, sau đó tìm cách trộn dần chúng với nhau thành các Run có thứ tự có chiều dài tăng dần cho đến khi chỉ còn một Run thì quá trình sắp xếp kết thúc.
Ta có giải thuật sau đây để trộn 2 Run X và y cùng thứ tự có chiều dài lần lượt là m và n thành một Run z có chiều dài là m + n.
Procedure Merge;
Var
     i, j, k: integer;
Begin
     i:= 1;
     j:= 1;
     k:= 1;
     while (i <= m) and (j <= n) do
          Begin
               If x[i] < y[j] then
                     Begin
                         z[k]:= x[i];
                         i := i + 1;
                     end;
              Else
                    Begin
                        z[k]:= y[j];
                        j := j + 1;
                    end;
              k:= k + 1;
        end;
    while i <= m do
         Begin
            z[k] := x[j];
            k := k + 1;
            i := k + 1;
            i := i + 1;
        end;
    while j <= n do
        Begin
            z[k]:= y[j];
            k := k + 1;
            j := j + 1;
        end;
End;
Cụ thể là nếu ta phải sắp xếp dãy: a[l], a[2], a[n].
Ta sử dụng 2*n phần tử được chia thành hai vùng. Vùng 1 gồm các phần tử a[l]..a[n], vùng 2 gồm các phần tử a[n+1]..a[2*n|. Ta trộn các Run từ vùng này và phân phối vào vùng kia. Khi trộn và phân phối, ta trộn các Run ngược chiều nhau của vùng trộn và phân phối luân phiên vào 2 đầu của vùng phân phối bước kế tiếp dễ trộn hơn. Quá trình sắp xếp sẽ kết thúc nếu vùng phân phối chỉ còn một Run. Khi kết thúc, nếu vùng phân phối gồm các phần tử a[n+l]..a[2*n] thì ta chép dãy a[n+1]..a[2*n] vào dãy a[l]..a[n].
* Ví dụ:
Sắp xếp dãy số:
39      50      7        37      89      13      1        62
• Bước 1: Vùng 1 là vùng trộn, vùng 2 là vùng phân phối:
Vùng 1:       39      50      7        37      89      13      1        62
                   ->      ->      ->      ->      <-      <-      <-      <-
Vùng 2:       39      62      7        13      89      37      50      1
                   ———>      ———>      <———      <———
• Bước 2: Vùng 2 là vùng trộn, vùng 1 là vùng phân phối:
Vùng 2:       39      62      7        13      89      37      50      1
                   ———>      ———>      <———      <———
Vùng 1:       1        39      50      62      89      37      13      7
                   ————————>      <————————
Bước 3: Vùng 1 là vùng trộn, vùng 2 là vùng phân phối:
Vùng 1:       1        39      50      62      89      37     13      7
                   ——————————————————>
Vùng 2:       1        7        13      37      39      50      62      89
• Bước 4: Chép các phần tử của vùng 2 vào vùng 1:
Vùng 2:       1        7        13      37      39      50      62      89
Vùng 1:       1        7        13      37      39      50      62      89
* Thể hiện bằng PASCAL:
CHÚ Ý:
• Ta khai báo:
Var a: array[1..2* n] of item ;
Đặt up: Bollean
     up = True: vùng 1 là vùng trộn, vùng 2 là vùng phân phối.
     up = false: vùng 2 là vùng trộn, vùng 1 là vùng phân phối.
     d: cho biết chiều phân phôi
     d = 1: chiều phân phôi tăng dần.
     d = -1: chiều phân phối giảm dần.
     p = chiều dài của run khi trộn.
     m = số phần tử chưa được trộn và phân phối.
     s, t = chiều dài của hai run đang trộn.
Vùng trộn  
Vùng phân phối  
• Cụ thể là:
Procedure Merge_Sort;
Var
     up: Bollean;
     i, j, k, q, t, r, s, d, p: integer;
Begin
     up := true;
     p := 1
     repeat
          d := 1;
          m := n;
          if up then
             Begin
                 i := 1; j := n;
                 k := n + 1; q := 2* n
             end
         else
             Begin
                 i:= n + 1; j:= 2 * n;
                 k:= 1; q:= n
             end;
         Repeat
              if m >= p then s := p else s := m; m:= m - s
'             while (s < > 0) and (r < > 0) do
              Begin
                   if a[i].key < a[j].key then
                      Begin
                           a[k] := a[i];
                           i := i + 1; s := s - 1;
                   end;
               else
                   Begin
                       a[k]:= a[j];
                       j := j - 1;
                       r := r - 1;
                  end;
               k:= k + d;
          end;
          while s < > do
                    Begin
                        a[k]:= a[i];
                        k := k + d;
                        i := i + 1;
                        s := s - 1;
                   end;
                   while r < > 0 do
                            Begin
                                a[k]:= a[j];
                                k:= k + d;
                                j := j - 1;
                                r := r - 1;
                           end;
                 d := -d;
                 t := k; k := q; q := 1;
             until m = 0;
             up :=  not up;
               p := 2*p
             until p >= n;
             if not up then
             For i := 1 to n do a[i]:= a[i + n]
end;

3. SẮP XẾP NGOÀI (SẮP XẾP TẬP TIN)
a) Khái niệm
Tất cả các phương pháp sắp xếp trong đã trình bày ở trên đều đòi hỏi phải đưa toàn bộ dữ liệu cần sắp vào bộ nhớ chính nên không thể dùng để sắp thứ tự các tập tin có chiều dài tương đối lớn vì không thể nạp toàn bộ tập tin vào bộ nhớ chính để sắp xếp, do đó ta phải có phương pháp khác thích hợp cho việc sắp xếp các tập tin.
Phương pháp căn bản để sắp xếp một tập tin là:
- Phân chia tập tin nguồn thành các tập tin nhỏ hơn,
- Nạp vào các tập tin đó vào bộ nhớ chính.
- Dùng các phương pháp sắp xếp trong để sắp xếp chúng thành các run.
- Trộn các run này lại và đưa vào tập tin đích. 
Trong đó hai bước quan trọng nhất là:
- Tạo các run ban đầu.
- Trộn các run với nhau.
Để đơn giản hóa vấn đề ở đây ta chỉ xét các phương pháp trộn run kích thước cố định của dãy.
b) Ví dụ
Ta xét 3 tập tin f[0], i[1], f[2] với f[0] là tập tin cần sắp xếp. Ta sẽ phân phối các run của f[0]ư và f[l], f[2] và trộn các run này vào tập tin f[0]. Nếu sau khi trộn mà f[0] chỉ có một run thì kết thúc thuật giải. Ngược lại nếu f[0] có nhiều hơn một run thì ta lặp lại bước phân phôi và trộn các run.
Ban đầu, f[0] chứa các khóa:
17 31 05 59 13 41 43 67 11 23 29 47 03 07 71 02 19 57 37 61
• Bước 1: Phân phối các run có chiều dài bằng 1 của f[0] vào f[1] và f[2]
f[1]    17   05   13   43   11   29   03   71   19   37
f[2]    31   59   41   67   23   47   07   02   57   61
• Bước 2: Trộn các run của f[1] và f[2] vào f[0]
F[0]   17 31   05 59    13 41    43 67   11 23    29 47
          03 07   02 71    19 57    37 61
• Bước 3 :    Phân phối các run cỏ chiều dài bằng 2 của f[0] vào f[l] và f[2]
f[1]    13 31   14 41   11 23    03 07   19 57
f[2]    05 59   43 67   29 47    02 71   37 61
• Bước 4 :    Trộn các run         của f[l] và f[2] vào f[0]
f[0]    05 17 31 59             13 41 43 67    11 23 29 47
          02 03 07 71             19 37 57 61
• Bước 5 :    Phân phối các run có chiều dài bằng 4 của f[0] vào f[l] và f[2]        
f[l]     05 17 31 59             11 23 29 47   19 37 57 61
f[2]    13 41 43 67             02 03 07 71
• Bước 6: Trộn các run của f[1] và f[2] vào f[0]
f[0]    05 13 17 31    41 43 59 67   02 03 07 11
          23 29 47 71    19 37 57 61
• Bước 7: Phân phối các run có chiều dài bằng 8 của f[0] vào f[1] và f[2]
f[1]    05 13 17 31    41 43 59 67 19 37 57 61
f[2]    02 03 07 11    23 29 47 71
• Bước 8: Trộn các run của f[l] và f[2] vào f[0]
f[0]    02 03 05 07    11 13 17 23    29 31 41 43    47 59 67 71
          19 37 57 61
• Bước 9: Phân phối các run có chiều dài bằng 16 của f[0] vào f[1] và f[2]
f[1] 02 03 05 07 11 13 17 23 29 31 41 43 47 59 67 71
f[2] 19 37 57 61

• Bước 10: Trộn các run của f[1] và f[2] vào f[0]
f[0] 02 03 05 07 11 13 17 19 23 29 31 37 41 43 47 57
       59 61 67 71

Ta khai báo:
Type
     tape = file of item;
Var
f: array[0..2] of tape;
Gọi: n - số mẫu tin của tập tin f[0]
Thủ tục Distribute phân phối các run có chiều dài bằng p của f[0] luân phiên vào f[1] và f[2J.
c) Thể hiện bằng PASCAL:
Procedure Merge_Sort;
Var
     p, q, r, m: integer;
     x1, x2: item;
Procedure Distribute (p: integer);
{Phân phôi các run có chiều dài bằng p của f[0] vào f[1] và f[2]}
Var
     k, i: integer;
     buf: item;
begin
     reset (f[0]); rewrite (f[1]); rewrite (f[2]);
     k := 1;
     i := 0; .
while not eof (f[0]) do
     begin
         i := i + 1;
         read (f[0], buf);
         write (f[k], buf);
         if i = p then
         begin
             i := 0;
             if k = 1 then k:= 2 else k:= 1
         end;
     end;
   rewrite (f[0]); reset (f[1]); reset (f[2]);
 end; {Distribute}
BEGIN (Merge.Sortl
   p:= 1;
   repeat
   {phân phối các run có chiều dài bằng p của f[0] vào f[1] và f[2]) ;
    Distribute(p)
    m:= n;
    read (f[1], x1) ; {run q}
    read (f[2], x2) ; {run r}
    repeat 
    if m >= p then q := p else q := m;
    m := m - q;
    if m >= p then r := p else r := m;
    m := m - r;
    while (p < > 0) and (r < > 0) do {chưa hết run q và run r}
         if x1.key < x2.key then
             begin
                write (f[0], x1);
                q := q - 1;
                if not eof (f[1]) then read (f[1], x1) ;
             end;
          else
              begin
                 write (f[0], x2);
                  r := r - 1;
                  if not eof (f[2]) then read x2):
              end;
          while q < > 0 do {chưa hết run q}
              begin
                  write (f[0], x1);
                  q := q - 1;
                  if not eof (f[1]) then read (f[1], x1);
              end;
          while r < > 0 do {chưa hết run r}
               begin
                  write (f[0], x2);
                  r := r - 1;
                  if not eof (f[2] then read (f[2], x2) ,
               end;
         until m = 0;
         p := 2*p ; {tăng chiều dài của run}
    until p >= n;
END;

 
Bản quyền bài viết thuộc về Sachgiai.com. Ghi nguồn Sách giải.com khi đăng lại bài viết này.

  Ý kiến bạn đọc

THÀNH VIÊN

Hãy đăng nhập thành viên để trải nghiệm đầy đủ các tiện ích trên site
Kênh Bóng đá trực tiếp hôm nay miễn phí
Kênh
90Phut TV full HD ⇔ 32win
RR88 ⇔ YO88 ⇔ bk8 ⇔ 123b

Vmax ⇔ SV388 ⇔ cakhiatv ⇔ bet88
789f ⇔ Cakhia TV ⇔ rikvip ⇔ 8x bet
https://qq887p.com/ ⇔ v9bet ⇔ okvip
b52club ⇔ Kkwin ⇔  ⇔ Link MB66
https://88betcom.pro/ ⇔ 8x bet ⇔ 33win
789BET ⇔ shbet ⇔ 32 win ⇔ RR88
MB66 ⇔ Nổ Hũ ⇔ BL555 ⇔ b52 club
https://789betcom0.com/ ⇔ https://hi88.baby/
HZ88 ⇔ đá gà ⇔ luongsontv ⇔ SHBET
hi88.biz ⇔ qq88 ⇔ i9 Bet ⇔ go88
f168 ⇔ 789F ⇔ j88 ⇔ 789win ⇔ 98win
88clb ⇔ 789win ⇔ HUBET ⇔ GK88
F168 ⇔ bet88 ⇔ QQ88 ⇔ bk8 ⇔ bk8
ee88 ⇔ iwinclub ⇔ MBET ⇔ net88
KING88 ⇔ soc88 ⇔ https://j88t3.com/
https://hi88.gives/ ⇔ 23win ⇔ 8kbet
78win ⇔ hi88 ⇔ https://fun88.social/
https://qq88z.net/ ⇔ I9BET ⇔ 7Club
https://qq88.fun/ ⇔ f168 ⇔ HUBET
daga ⇔ SHBET ⇔ keo nha cai ⇔ bl-555.site
https://bshbet.com/ ⇔ https://uk88.rocks
MM88 ⇔ Au88 ⇔ 88AA ⇔ 8kbet
https://luongson117.tv/ ⇔ https://hello8880.net/
xin 88 ⇔ https://78win01.locker/ ⇔ uu88
NOHU ⇔ bj88 live ⇔ 32win ⇔ Kuwin
Bay789 ⇔ w388 ⇔ sv388 ⇔ 23win
WW88 ⇔ https://f168.com.co/
7m ⇔ kuwin ⇔ https://789club24.com/
https://33win103.com/ ⇔ https://f168.group/
https://33win102.com/ ⇔ https://789p.co.com/
https://33win100.com/ ⇔ https://hi88.tours/
https://myeat.net/ ⇔ https://hi88.report/
https://58win1.info/ ⇔ https://f168.giving/
https://new88c.co/ ⇔ https://hello880.net/
https://789club60.com/ ⇔ 789WIN
F168 ⇔ E2BET ⇔ f168 ⇔ f168
88Vv ⇔ https://789club24.com/ ⇔ hi88com
 ⇔ 8xbet ⇔ Kubet ⇔ j88 ⇔ EV88
XX88 ⇔ KUBET ⇔ 99OK ⇔ RR88
88i ⇔ 33win ⇔ http://hi88.uno/
https://33win101.com/ ⇔ SHBET ⇔ Min88
hi88 ⇔ https://shbet.gg/ ⇔ SHBET
https://33winpro.me/ ⇔ https://23win.build
alo789 ⇔ hubet ⇔ UU88 ⇔ TG88
https://shbet.solar/ ⇔ https://daga.help/
https://pg88.ca/ ⇔ 
lương sơn tv ⇔ https://ww88i.club/
https://hi88.voyage/ ⇔ https://bk8co.net/
cakhiatv ⇔ https://23wincom.info
https://hi88o.com/ ⇔ https://f168.law/
https://88bett.vip/ ⇔ https://j88.ventures/
https://rcc.eu.com/ ⇔ https://j88com.limited/
New88 ⇔ https://j88.now/ ⇔ hi88
kubet ⇔ Okking ⇔ https://33win.software/
https://ww88star.com/ ⇔ vankhanhtv ⇔ ww88
https://88vvcom.net/ ⇔ https://okwin.technology/
bong88 ⇔ j88 ⇔ j88 ⇔ sunwin ⇔ sunwin
No hu ⇔ 888b ⇔ MM88 ⇔ go 88
kuwin ⇔ nhà cái uy tín ⇔ rwin ⇔ dt68
MM88 ⇔ Nh88 ⇔ RR88 ⇔ game sunwin
789win ⇔ https://ok365.fitness/
https://xx88.ink/ ⇔ https://79king.is/
S666 ⇔ xocdia88 ⇔ Sun Win ⇔ Vmax
tỷ lệ kèo nhà cái hôm nay ⇔ Vivu88
https://j88ss.com ⇔ https://qq88.studio/
https://mm88.blue/ ⇔ Link vào Kingfun
 ⇔ https://cakhiatv88.net/
https://shbet.is/ ⇔ https://13win.london/
https://789win.fund/ ⇔ https://nhacaiuytinso1.net/
nohu ⇔ https://abcvip.ru.com/ ⇔ RR88
https://king88.international/ ⇔ 33win ⇔ 98WIN
https://qq88.racing/ ⇔ https://j88uk.com
https://hubest.co/ ⇔ https://ww88.engineer/
https://muranoglass-shop.cn.com/ ⇔ J88
soi kèo nhà cái ⇔ https://king88.giving/
https://bet88.ventures/ ⇔ trực tiếp bóng đá
https://king88clb.com ⇔ E2bet ⇔ KUBET
https://sh-bet.com/ ⇔ 8xbet app ⇔ King 88
https://32win.vc/ ⇔ 88bet ⇔ PG88 ⇔ PG88
EE88 ⇔ B52Club ⇔ B52 Club ⇔ HB88
HB88 ⇔ Vin777 ⇔ SV388 ⇔ QQ88 ⇔ 32win
https://vankhanhtvv.com/ ⇔ https://luck8.world/
23WIN ⇔ bubet ⇔ https://u888lm.com/
tỷ lệ kèo nhà cái ⇔ 78win ⇔ https://789win01.club/
https://32win.domains/ ⇔ https://sv388.engineering/
https://8kbetbh.com/ ⇔
Bạn đã không sử dụng Site, Bấm vào đây để duy trì trạng thái đăng nhập. Thời gian chờ: 60 giây