Chào mừng các em đến lập trình Pascal

Một số thuật toán sắp xếp trong mảng

 Sắp xếp:

1. Khái niệm:

a) Sắp xếp là một quá trình tổ chức lại một dãy các dữ liệu theo một trật tự nhất định.

          b) Mục đích của việc sắp xếp là nhằm giúp cho việc tìm kiếm dữ liệu một cách dễ dàng và nhanh chóng.  Sắp xếp là một việc làm hết sức cơ bản và được dùng rộng rãi trong các kĩ thuật lập trình nhằm sử lý dữ liệu.

          c) Các giải thuật sắp xếp được phân chia thành hai nhóm chính là:

  - Sắp xếp trong (hay sắp xếp mảng).

  Toàn bộ cơ sở dữ liệu cần sắp xếp phải được đưa vào bộ nhớ chính của máy tính. Do đó nó thường được sử dụng khi khối lượng dữ liệu không vượt quá dung lượng bộ nhớ chính.

  Nhóm sắp xếp trong bao gồm các phương pháp :

    * Phương pháp đếm.

    * Phương pháp chèn.

    * Phương pháp chọn.

    * Phương pháp đổi chổ.

    * Phương pháp trộn.

  - Sắp xếp ngoài (hay sắp xếp tập tin).

  Vận dụng trong trường hợp ta phải sắp xếp các tập tin chứa nhiều mẫu tin và mỗi mẫu tin có chiều dài tương đối lớn do đó ta không thể nạp toàn bộ vào bộ nhớ chính để sắp xếp thứ tự. Vì vậy ta phải có những phương pháp thích hợp cho việc sắp xếp tập tin.

2. Sắp xếp trong:

  a) Khái niệm:

 Cấu trúc dữ liệu thích hợp cho các phần tử cần sắp xếp thứ tự là Record. Mỗi phần tử có hai vùng đặc trương là: Vùng Key  để chứa khoá của phần tử và được sử dụng trong các giải thuật tìm kiếm, vùng info dùng để chứa đữ liệu các phần tử.

    Ta khai báo :

       Type

        Item = Record

          key  :  Integer;

          Info :  Integer;

        End;

      Var

        A : Array[1..n] of Item;

 Khoá của phần tử có thể là chữ hoặc số.

  Yêu cầu giải thích là dùng ít vùng nhớ và thời gian thực hiện nhanh.

  b) Phương pháp đếm (Counting sort)

  * Giải thích:

  Nội dung của phương pháp này là đếm các phần tử có khoá nhỏ hơn hay bằng khoá của các phần tử A[i]. Nếu có j phần tử có khoá nhỏ hơn khoá của phần tử A[i] thì phần tử A[i] sẽ có vị trí theo thứ tự (j+1) trong dãy đã có thứ tự.

  Trong giải thuật, ta dùng mảng Count[i] ( i = 1, 2, .. n ) với Count[i] cho biết số phần tử có khoá nhỏ hơn khoá của phần tử A[i]. Như vậy Count[i+1] là vị trí của phần tử A[i] trong dãy đã có thứ tự.

  * Ví dụ:

  Sắp xếp dãy     2 3 1 5 2 7 6 9 4

                    i:    1 2 3 4 5 6 7 8

         Count:      2 0 4 1 6 5 7 3

  Như vậy phần tử có khoá 9 ở vị trí 8 vì Count[9]=7.

  * Thể hiện bằng Pascal:

    Procedure Count_Sort;

      Var

        Count : Array[1..n] of Integer;

        A     : Array[1..n] of Item;

        i,j   : Integer;

      Begin

        For i := 1 to n do Count[i] := 0;

        For i := n downto 2 do

          For j := i-1 downto 1 do

            If A[i].Key < A[j].Key Then

              Count[j] := Count[j] + 1

            Else Count[i] := Count[i] + 1;

        For i := 1 to n do S[Count[i] + 1] := A[i];

        For i := 1 to n do A[i] := S[i];

      End;

 c) Phương pháp chèn (Insertion Sort)

  * Giải thích:

  Nội dung của phương pháp này là giả sử ta có dãy  A[1]..A[i-1] đã có thứ tự, có phải xác định vị trí thích hợp của phần tử A[i] trong dãy A[1]..A[i - 1] bằng phương pháp tìm kiếm tuần tự từ A[i - 1] trở về A[1] để tìm ra vị trí thích hợp của A[i]. Ta chèn A[i] vào vị trí này và kết quả là đãy A[1] .. A[i] có thứ tự. Ta áp dụng cách làm này với i = 2, 3, ..., n.

  * Ví dụ:

  Ta phải sắp xếp dãy số:

          39  50   7  37  89  13   1  62

  i=2   39  50   7  37  89  13   1  62

  i=3   39  50   7  37  89  13   1  62

  i=4    7  39  50  37  89  13   1  62

  i=5    7  37  39  50  89  13   1  62

  i=6    7  37  39  50  89  13   1  62

  i=7    7  13  37  39  50  89   1  62

  i=8    1   7  13  37  39  50  89  62

           1   7  13  37  39  50  89  62

  * Thể hiện bằng Pascal:

    Procedure Insertion_Sort;

      Var

        x     : Item;

        i,j   : Integer;

      Begin

        For i := 2 to n do

          Begin

            x := A[i];

            A[0] := x;

            j := j - 1;

            While x.Key < A[j].Key do

              Begin

                A[j+1] := A[j];

                j := j - 1;

              End;

            A[j+1] := x;

          End;

      End;

  d) Phương pháp chọn (Selection Sort)

  * Giải thích:

  Nội dung của phương pháp này là ở bước thứ i (i = 1, 2, 3, ..., n-1 ) ta lựa chọn phần tử nhỏ nhất trong dãy A[i]..A[n] rồi đổi chổ phần tử này với phần tử A[i]. Cuối cùng ta sẽ có dãy A[1]..A[n] có thứ tự.

  * Ví dụ:

  Ta phải sắp xếp dãy số :

          39  50   7  37  89  13   1  62

  i=1   39  50   7  37  89  13   1  62

  i=2    1  50   7  37  89  13  39  62

  i=3    1   7  50  37  89  13  39  62

  i=4    1   7  13  37  89  50  39  62

  i=5    1   7  13  37  89  50  39  62

  i=6    1   7  13  37  50  50  39  62

  i=7    1   7  13  37  39  50  89  62

           1   7  13  37  39  50  89  62

  * Thể hiện bằng Pascal:

    Procedure Selection_Sort;

      Var

        x      : Item;

        i,j ,k : Integer;

        min    : Integer;

      Begin

        For i := 2 to n-1 do

          Begin

            min := A[i].Key;

            k   := i;

            For i := 1 to n-1 do

              For j := i+1 to n do

                If A[j].Key < min Then

                  Begin

                    min := A[j].Key;

                    k   := j;

                  End;

            x := A[k];

            A[k] := A[i];

            A[i] := x;

          End;

      End;

  e) Phương pháp đổi chỗ:

  Có rất nhiều phương pháp sắp xếp dựa trên việc đổi chỗ giữa 2 phần tử của dãy. Sau đây chúng ta xét các phương pháp:

    - Bubble Sort.

    - Shake Sort.

    - Sell Sort.

    - Quick Sort.

 

  * Bubble Sort:

  * Giải thích:

  Nội dung của phương pháp này là duyệt các dãy A[1], ..., A[n]. Nếu A[i].Key > A[i+1].Key (i = 1, 2, 3, ..., n-1)#0 thì ta đổi chỗ A[i].Key với phần tử A[i+1].Key. Lập lại quá trình duyệt dãy này cho đến khi không còn việc đổi chổ của hai phần tử.

  Chú ý rằng bất cứ lúc nào phần tử nhỏ nhất cũng gặp trước tiên. Nó như những bột khí nhẹ sẽ nổi lên trên khi đun nước. Sau đó ở thứ hai phần tử nhỏ thứ 2 sẽ được đặ vào đúng một vị trí. Vì vậy sắp xếp nổi bột thao tác như một kiểu sắp xếp chọn, mặc dù nó không làm nhiều việc hơn để đưa từng phần tử vào đúng vị trí.

 * Ví dụ:

  Ta phải sắp xếp dãy số:

           39  50   7  37  89  13   1  62

  Bước   0   1   2   3   4   5   6   7

        50   1   1   1   1  13   1  62

        39  39   7   7   7   7   7   7

         7  50  39  13  13  13  13  13

        37   7  50  39  37  37  37  37

        89  37  13  50  39  39  39  39

        13  89  37  37  50  50  50  50

         1  13  89  62  62  62  62  62

        62  62  62  89  89  89  89  89

  * Thể hiện bằng Pascal:

    Procedure Bubble_Sort;

      Var

        x     : Item;

        i,j   : Integer;

      Begin

        For i := 2 to n do

          For j := n downto i do

            If A[j-1].Key > A[j].Key Then

              Begin

                x := A[j-1];

                A[j-1] := A[j];

                A[j-1] := x;

              End;

      End;

 

  * Cải tiến:

  Ta nhận thấy rằng nếu ở một lần duyệt dãy nào đó mà không co s xẩy ra sự đổi chổ giữa hai phần tử thì dãy dang sắp đã có thứ tự và giải thuật kết thúc.

  Ta có thể cài đặt cờ để ghi nhận điều này và có chương trình sau:

    Procedure Bubble_Sort2;

      Var

        x     : Item;

        i     : Integer;

        flag  : Boolean;

      Begin

        flag := true;

        While flag do

          Begin

            flag := False;

            For i := 1 to n-1 do

              If A[i].Key > A[i+1].Key Then

                Begin

                  x := A[i];

                  A[i] := A[i+1];

                  A[i+1] := x;

                End;

          End;

      End;

 

  f* Shake Sort:

  * Giải thích:

  Phương pháp này là một cải tiến của phương pháp Bubble Sort theo hướng "Không những phần tử nhẹ nổi lên trên mà cả phần tử nặng cũng xuống dưới" giống như khi ta rung"rung" một cái nồi và thuật toán sắp xếp phải được điều khiển cả hai quá trình "nổi lên" và "chìm xuống" này một cách tự giác. Muốn vậy ta phải ghi nhớ lần đổi chổ cuối cùng khi duyệt dãy từ trên lên và khi duyệt từ trên xuoóng để quyết định chu trình kế tiếp sẽ duyệt từ đâu đến đâu.

  * Ví dụ:

  Sắp xếp dãy số:

        39  50   7  37  89  13   1  62

    d =  2   3   3   4   4

    c =  8   8   7   7   4

        39   1   1   1   1

        50  39  39   7   7

         7  50   7  39  13

        37   7  37  13  37

        89  37  50  37  39

        13  89  13  50  50

         1  13  62  62  62

        62  62  89  89  89

  * Thể hiện bằng Pascal:

    Procedure Shake_Sort;

      Var

        x        : Item;

        i,k,d,c  : Integer;

      Begin

        d := 2;

        c := n;

        k := n;

        Repeat

          For i := c downto d do

            If A[i-1].Key > A[i].Key Then

              Begin

                x := A[i-1];

                A[i-1] := A[i];

                A[i-1] := x;

                k := i;

              End;

          d := d + 1;

          For i := d to c do

            If A[i-1].Key > A[i].Key Then

              Begin

                x := A[i-1];

                A[i-1] := A[i];

                A[i-1] := x;

                k := i;

              End;

          c := k-1;

        Until d>c;

      End;

 

g.  * Shell Sort:

  * Giải thích:

  Các phương pháp sắp xếp dã trình bày ở trên nói chung đều di chuyển mỗi phần tử đi một vị trí trong mỗi bước. Phương pháp Shell Sort dựa trên ý tưởng chính là hoán các phần tử ở xa nhau. Để làm được việc đó ta cần phải sắp các tập tin để nó có tính chất là việc lấy mọi phần tử thứ h (bắt đầu từ vị trí bất kì nào) cũng đều cho ra tập tin đã sắp. Một tập tin như vậy được gọi là sắp theo độ dài bước h. Một cách nói khác, một tập tin dược sắp theo độ dài bước h là tập tin được sắp độc lập với nhau, đan xen vào nhau. Bằng cách sắp xếp theo độ dài bước h ứng với vài giá trị h khá lớn, chúng ta có thể di chuyển các phần tử ở những khoảng cách xa nhau trong mảng và vì vậy dễ dàng hơn để sắp xếp độ dài bước h các giá tri nhỏ hơn. Dùng thủ tục cho bất kì một dãy các giá trị của h tận cùng là 1 sẽ cho ra một tập tin đã sắp xong: Dó chính là  Shell Sort.

  * Ví dụ:

  Ta phải sắp xếp dãy số:

           39  50   7  39  89  13   1  62

  Bước 1: 4-Sort

           39  50   7  39  89  13   1  62

           39  13   1  37  89  50   7  62

  Bước 2: 2-Sort

           39  13   1  37  89  50   7  62

            1  13   7  37  39  50  89  62

  Bước 3: 1-Sort

            1  13   7  37  39  50  89  62

            1  7   13  37  39  50  89  62

 

  * Thể hiện bằng Pascal:

  Chú ý:

  - Ta dùng dãy phụ chứa dộ tăng h[i], ..., h[t] để điều khiển quá trình sắp xếp thứ tự với h[t]=1. Việc chộn các độ tăng thích hợp sẽ làm giảm thời gian sắp thứ tự.

  - Dặt h1 = h[1] ta phải khai báo dãy a như sau:

      A : Array[1..n] of Item;

  các phần tử A[i] (i<=0) là các lính canh. Sau đây ta chọn:

      h[1] = 9, h[2] = 5, h[3] = 3, h[4] = 1

    Procedure Shell_Sort;

      Const

        t = 4;

      Var

        x        : Item;

        i,j,k,s,m: Integer;

        h        : Array[1..t] of Integer;

      Begin

        h[1] = 9;

        h[2] = 5;

        h[3] = 3;

        h[4] = 1;

        For m := 1 to t do

          Begin

            k := h[m];

            s := -k;

            For i := k+1 to n do

              Begin

                x := A[i];

                j := i - k;

                If s = 0 Then s:=-k;

                s := s + 1;

                A[s] := x;

                While x.Key<A[j].Key do

                  Begin

                    A[j+k] :=A[j];

                    j := j - k;

                  End;

                A[j+k] := x;

              End;

          End;

      End;

h. Quick Sort:

  * Giải thích:

  Nội dung của phương pháp này là chọn phần tử x ở giữa của dãy làm chuẩn để so sánh. Ta phân hoạch dãy này thành 3 dãy con liên tiếp nhau:

  - Dãy con thứ nhất gồm phần tử có khoá nhỏ hơn x.key.

  - Dãy con thứ hai gồm các phần tử có khoá bằng x.key.

  - Dãy con thứ ba gồm các phần tử có khoá lớn hơn x.key.

  Sau đó áp dụng giải thuật phân hoạch này cho dãy con thứ nhất nhất và dãy con thứ ba, nếu các dãy con có nhiều hơn một phần tử (Đệ qui).

  Cụ thể là xét một doạn của dãy từ thành phần L đến thành phần thứ R.

  - Lấy giá trị của thành phần thứ (L+R) Div 2 gán vào biến X.

  - Cho i ban đầu là L.

  - Cho j ban đầu là R.

  - Lập lại.

    * Chừng nào còn A[i] < X thì tăng i.

    * Chừng nào còn A[j] > X thì giảm j.

    * i<=j thì

       + Hoán vị A[i] và A[j]

       + Tăng i

       + Giảm j

  Cho đến khi i>j

       + Sắp xếp đoạn từ A[L] đến A[j]

       + Sắp xếp đoạn từ A[i] đến A[R]

  * Ví dụ:

  Sắp xếp dãy số:

        39  50   7  37  89  13   1  62

    X =  37

    Sau 2 lần đổi chổ ta được dãy:

         1  13   7  37  89  50  39  62

 

    Xử lý dãy con:

         1  13   7

    Ta được:

         1   7  13

    Sử lý dãy con:

         89 50  39  62

    Ta được:

         39  50  89  62

         39  50  62  89

    Vậy dãy đã sắp xếp là:

         1   7  13  39  50  62  89

  * Thể hiện bằng Pascal:

  Để đơn giản ta viết thủ tục sắp một mảng số nguyên được truyền tham biến.

    Procedure Quick_Sort(Var A : Array[1..n] of Integer);

      Procedure Sort(L,R : Integer);

        Var

          i,j,Tg,X : Integer;

        Begin

          X := A[(L+R) Div 2];

          i  := L;

          j := R;

          Repeat

            While (A[i] < X) do Inc(i);

            While (A[j] > X) do Dec(j);

            If i <= j Then

              Begin

                Tg := A[i];

                A[i] := A[j];

                A[j] := Tg;

                Inc(i);

                Dec(j);

              End;

          Until i>j;

          If L < j Then Sort(L,j);

          If i < R Then Sort(i,R);

        End;

      Begin

        Sort(1,n);

      End;

i. 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 số cần sắp thành các dãy con đã có thứ tự(goi là các Run) và có số phần tử là luỹ thừa 2 sau đó tìm cách trộn dần chúng với nhau thành các Run có thứ tự 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[j];

                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    := i + 1;

          End;

        While j<=n do

          Begin

            Z[k] := X[j];

            k    := k + 1;

            j    := j + 1;

          End;

    End;

  Cụ thể là nếu ta phải sắp xếp dãy: A[1], A[2], ...,A[n].

  Ta phải sử dụng 2*n phần tử được chia thành 2 vùng. Vùng 1 gồm các phần tử A[1] .. 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+1] .. A[2*n] thì ta chép dãy A[n+1] .. A[2*n] vào dãy A[1] .. A[n]

   Thể hiện bằng Pascal

    Procedure mergesort ( l , r : integer );

        Var i , j , k , m: integer; 

             Begin

                 If r-l>0 then

                   Begin

                     m := (r+l) div 2;

                     mergesort (l,m); mergesort (m+1,r);

                     for i:=m downto l do b [i] := a [i];

                     for j:=m+1 to r do b [r+m+1-j] := a [j];

                     for k := l to r do

                        if b[i] < b [j] then

                           begin  a [k] := b[i];  i:=i+1; end else

                           begin  a [k] := b[j];  j:=j-1; end;

                           end;

                   End;

             End;

 

 

Thêm, chỉnh sửa nội dung, hình ảnh...

Chỉnh sửa website một cách dễ dàng.

Hãy click vào biểu tượng bút chì để mở danh sách các chức năng.

Bạn có thể thêm, sửa, xóa các phần tử của trang web như các biểu mẫu, bảng, hình ảnh... Bạn cũng có thể chỉnh sửa một phần từ bằng cách click vào phần tử đó.

Bạn có thể dễ dàng thay đổi vị trí các phần tử bằng các thao tác kéo thả rất đơn giản.