[PASCAL] Các thuật toán sắp xếp trong Pascal - Cóc Blog

Tóm Tắt

Các thuật toán sắp xếp trong Pascal :

Selection Sort, Insert Sort, Bubble Sort, QuickSort

Sắp xếp là thuật toán căn bản không chỉ trong ngôn ngữ lập trình Pascal mà còn trong nhiều lĩnh vực công nghệ khác. Bài viết sau sẽ để cập đến một số thuật toán sắp xếp bằng ngôn ngữ Pascal.

Bạn đang đọc: [PASCAL] Các thuật toán sắp xếp trong Pascal – Cóc Blog

cac-thuat-toan-sap-xep-trong-pascal

1. Bubble Sort ( Sắp xếp nổi bọt )

Ý tưởng : Giả sử có mảng có n thành phần. Chúng ta sẽ thực thi duyệt từ cuối lên đầu, so sánh 2 thành phần kề nhau, nếu chúng bị ngược thứ tự thì đổi vị trí, việc duyệt này khởi đầu từ cặp thành phần thứ n-1 và n. Tiếp theo là so sánh cặp thành phần thứ n-2 và n-1, … cho đến khi so sánh và đổi chỗ cặp thành phần thứ nhất và thứ hai. Sau bước này thành phần nhỏ nhất đã được nổi lên vi trí trên cùng ( nó giống như hình ảnh của những “ bọt ” khí nhẹ hơn được nổi lên trên ). Tiếp theo thực thi với những thành phần từ thứ 2 đến thứ n .

Procedure bubblesort(var amang; Ninteger);
begin
        var i,j integer;
        for i=2 to N do
        for j=N down to i do
        if (a[j]  a[j-1])
then
    hoanvi(a[j-1],a[j]);
end;

2. Selection Sort ( Sắp xếp chọn )

Ý tưởng : Chọn thành phần nhỏ nhất trong n thành phần bắt đầu, đưa thành phần này về vị trí đúng là tiên phong của dãy hiện hành. Sau đó không chăm sóc đến nó nữa, xem dãy hiện hành chỉ còn n-1 thành phần của dãy bắt đầu, khởi đầu từ vị trí thứ 2. Lặp lại quy trình trên cho dãy hiện hành đến khi dãy hiện hành chỉ còn 1 thành phần. Dãy khởi đầu có n thành phần, vậy tóm tắt sáng tạo độc đáo thuật toán là triển khai n-1 lượt việc đưa thành phần nhỏ nhất trong dãy hiện hành về vị trí đúng ở đầu dãy .

Các bước triển khai như sau :

Bước 1 : i = 1

Bước 2 : Tìm thành phần a [ min ] nhỏ nhất trong dãy hiện hành từ a [ i ] đến a [ n ]

Bước 3: Hoán vị a[min] và a[i]

Xem thêm: Background trong CSS

Bước 4 : Nếu i < = n-1 thì i = i + 1 ; Lặp lại bước 2 trái lại : Dừng. n-1 thành phần đã nằm đúng vị trí .

Procedure seletionsort ( var a : mang ; N : byte ) ;
Procedure seletionsort(var a:mang; N:byte);
var i,j: byte; min: integer;
begin
        for 1:=1 to N-1 do 
        if (a[j] < a[min] then min:=j;
        if (min <> i) then hoanvi (a[min]; a[i];
end;

Procedure hoanvi(var x,y: integer);
var tam:integer
begin
        tam:=x
        x:=y
        y:=tam
end;

3. Insert Sort

Procedure insertionsort(var a:mang, N:byte);
begin
        var pos,i: byte; x:integer;
        for i:=2 to N do
        begin
            x:=a[i]; pos:=i;
{sap xep tang dan}
while (pos>1 and a[pos-1]>x)do
    begin
        a[pos]:= a[pos-1]; dec(pos);
    end;
    a[pos]:= x;
end;
{sap xep giam dan}
while (pos>1)
    begin
        if(a[pos-1] > x)then
    begin
        a[pos]:= a[pos-1]; dec(pos);
    end;
    a[pos]:= x;

4. QuickSort

procedure Quicksort ( Var A: Mang);
     Procedure Sort( Left, Right: Integer);
            Var
                     i, j, k: Integer;
               Begin
                     i:= Left;
                     j:= Right;
                     k:= A[(Left + Right) Div 2];
                     Repeat
                       While A[i] < k Do Inc(i);
                       While k < A[j] Do Dec(j);
                       If i <> j Then
                             Begin
                                     HoanVi(A[i],A[j]);
                                     Inc(i);
                                     Dec(j);
                             end;
                     Until i > j;
                             If Left < j Then Sort(Left,j);
                             If i < Right Then Sort(i,Right);
              end;
   Begin
          Sort(Left; Right);
   End;

Admin

I'm Huy and the owner of this blog. I like design websites, like programming, like listening pop music, enjoy sharing. All feedback, problems, please contact me !