Ví dụ 2 bài 11. kiểu bảng

Ví dụ 2 :Sắp xếp dãy số nguyên bằng thuật toán tráo đổi.
Bước 1: Xác Định output, input
Input: Số nguyên dương N (N≤250), dãy số A gồm N số nguyên dương, mỗi số đều không vượt quá 500.
Output: Dãy số A đước sắp xếp thành dãy số không giảm.

Bước 2: Xác Định thuật toán
B1: Nhập n
B2: Nhập mảng n phần tử (ngẫu nhiên)
B3: j  n, nếu j < 2 thì xuất mảng, ngược lại thì xuống B4
B4: i  1, nếu i > j - 1 thì j j – 1, ngược lại thì xuống B5
B5: Nếu A[i] > A[i+1] thì tráo đổi A[i] và A[i+1]; i  i +1
Chú thích: j j – 1 lặp giảm; i  i +1 lặp tăng
? Tại sao j chạy từ n xuống 2 mà ko từ n xuống 1
! Vì nếu j = 1 thì khi for i:=1 to j -1 do thì i chạy từ 1 đến 0 là ko hợp lý
? Tại sao i chạy từ 1 đến j - 1 mà ko từ 1 đến j
! Vì nếu i = j thì khi xét điều kiện A[i] > A[i+1] không hợp lý (j là phần tử cuối, phía sau ko còn ptu nào để so sánh)
Nhận xét: Với thuật toán này thời gian chạy chương trình nhanh vì không phải xét dư các trường hợp. Cụ thể: với j chạy từ n xuống 2 có nghĩa là sau khi sắp xếp lần 1, giá trị cuối mảng là giá trị lớn nhất và ko cần sắp xếp nữa, sau đó thuật toán sẽ tiếp tục sắp xếp mảng còn lại. Tương tự, sau khi sắp xếp lần 2, giá trị kế cuối mảng là giá trị lớn thứ 2 …

Ví dụ: Với n = 5, ta có mảng sau:
7 -5 2 1 3
j = 5
i = 1:
A[1] > A[2] nên mảng:
-5 7 2 1 3
i = 2:
-5 2 7 1 3
i = 3:
-5 2 1 7 3
i = 4:
-5 2 1 3 7 Xong lần 1, phần tử cuối cùng có giá trị lớn nhất, lần tiếp theo chỉ sắp xếp mảng còn lại (trừ phần tử cuối):

-5 2 1 3
j = 4
i = 1:
-5 2 1 3
i = 2:
-5 1 2 3
i = 3:
-5 1 2 3
Xong lần 2 … Cuối cùng xuất mảng đã được sắp xếp

Program sapxep;
Uses crt;
Const Nmax = 250;
Type
ArrInt = array[1..Nmax] of integer;
Var N,I,j,t : integer;
A : ArrInt;
Begin
Clrscr;
Write(‘Nhap so luong phan tu cua day so, N = ‘);
Readln(N);
For i:=1 to N do (* Nhap cac phan tu*);
Begin
Write(‘nhap phan tu thu ‘,I,’=‘);
Readln(A[i]);
End;
For j:=N downto 2 do
For i:=1 to j -1 do
If A[i] > A[i+1] then
Begin (* trao doi A[i] va A[i+1]*)
t:= A[i];
A[i]:=A[i+1];
A[i+1]:=t;
End;
Writeln(‘ day so duoc sap xep la; ‘);
For i:=1 to N do write ( A[i] : 4);
Readln
End.
XIN CÁM ƠN CÁC BẠN ĐÃ CHÚ Ý LẮNG NGHE
~^-^~