Bài toán. Viết chương trình cho phép nhập n số sắp xếp và in ra các số đã nhập theo thứ tự tăng dần.
Program sapXep;
Var M: array[1..10] of integer;
i,j,n: byte;
tam: integer;
Begin
Write('Nhap so phan tu n:');Readln(n);
For i:=1 to n do
Begin Write('M[',i,']='); Readln(M[i]); End;
For i:=1 to n-1 do
For j:=i+1 to n do if M[j] <=M[i] then
Begin Tam:= M[i]; M[i]:=M[j]; M[j]:=tam; End;
Write('Sau khi sap xep: ');
For i:=1 to n do Write(M[i],';');
Readln;
End.
Chương trình trên thực hiện thuật toán sắp xếp chọn để sắp xếp mảng số nguyên M
theo thứ tự tăng dần. Dưới đây là mô tả cách chương trình hoạt động:
- Người dùng được yêu cầu nhập số phần tử của mảng (
n
) thông qua lệnhWrite('Nhap so phan tu n:'); Readln(n);
. - Một vòng lặp
for
được sử dụng để nhập các giá trị cho mảngM
. Trong mỗi vòng lặp, người dùng nhập giá trị cho phần tửM[i]
bằng lệnhWrite('M[',i,']='); Readln(M[i]);
. - Tiếp theo, hai vòng lặp
for
được sử dụng để thực hiện thuật toán sắp xếp chọn. Vòng lặp ngoài (for i:=1 to n-1 do
) duyệt qua từng phần tửM[i]
từ đầu đến trước phần tử cuối cùng. Vòng lặp trong (for j:=i+1 to n do
) duyệt qua các phần tửM[j]
từ phần tử ngay sauM[i]
đến phần tử cuối cùng. - Trong vòng lặp trong, sử dụng câu lệnh điều kiện
if M[j] <= M[i] then
để so sánh giá trị củaM[j]
vớiM[i]
. NếuM[j]
nhỏ hơn hoặc bằngM[i]
, thì các phần tử được hoán đổi vị trí bằng cách sử dụng biến tạmtam
. Cụ thể, lệnhTam:= M[i]; M[i]:=M[j]; M[j]:=tam;
được sử dụng để hoán đổi giá trị củaM[i]
vàM[j]
. - Sau khi kết thúc vòng lặp
for j
, một phần tử nhỏ nhất (hoặc lớn nhất) trong phần mảng chưa được sắp xếp từ vị tríi+1
đếnn
được đưa vào vị trí đúng sau phần tửM[i]
. - Quá trình trên được lặp lại cho đến khi tất cả các phần tử trong mảng được sắp xếp.
- Cuối cùng, mảng đã được sắp xếp được hiển thị thông qua lệnh
Write('Sau khi sap xep: '); For i:=1 to n do Write(M[i],';');
. - Chương trình kết thúc với lệnh
Readln;
để chờ người dùng nhấn Enter để thoát.
Lưu ý: Chương trình trên giới hạn số phần tử trong mảng là 10
Bạn có thể hiểu hơn về thuật toán này với phần mô tả dưới đây:
Thuật toán Sắp xếp chọn (Selection sort) hoạt động bằng cách tìm phần tử nhỏ nhất (hoặc lớn nhất) trong mảng và đặt nó vào vị trí đầu tiên (hoặc cuối cùng) của mảng. Sau đó, thuật toán tiếp tục tìm phần tử nhỏ nhất (hoặc lớn nhất) trong phần mảng chưa được sắp xếp và đặt nó vào vị trí thích hợp tiếp theo của mảng đã sắp xếp. Quá trình này được lặp lại cho đến khi toàn bộ mảng được sắp xếp.
Dưới đây là mô tả thuật toán Sắp xếp chọn:
- Bắt đầu với một mảng chưa được sắp xếp.
- Đặt biến
i
từ 1 đến(n-1)
(vớin
là số phần tử trong mảng). - Tìm phần tử nhỏ nhất (hoặc lớn nhất) trong phần mảng chưa được sắp xếp, từ vị trí
i
đếnn
. - Hoán đổi phần tử nhỏ nhất (hoặc lớn nhất) tìm được với phần tử ở vị trí
i
trong mảng. - Tăng giá trị của
i
lên 1 và quay lại bước 3 cho đến khii
đạt đến(n-1)
. - Kết quả là mảng đã được sắp xếp.
Trong mỗi bước, thuật toán Sắp xếp chọn tìm phần tử nhỏ nhất (hoặc lớn nhất) trong phần mảng chưa được sắp xếp để đưa nó vào vị trí thích hợp trong mảng đã sắp xếp. Quá trình này tiếp tục cho đến khi toàn bộ mảng được sắp xếp theo thứ tự tăng dần (hoặc giảm dần).