Sắp xếp tăng dần trong Pascal

7228
Lập trình Pascal

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:

  1. Người dùng được yêu cầu nhập số phần tử của mảng (n) thông qua lệnh Write('Nhap so phan tu n:'); Readln(n);.
  2. Một vòng lặp for được sử dụng để nhập các giá trị cho mảng M. Trong mỗi vòng lặp, người dùng nhập giá trị cho phần tử M[i] bằng lệnh Write('M[',i,']='); Readln(M[i]);.
  3. 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 sau M[i] đến phần tử cuối cùng.
  4. 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ủa M[j] với M[i]. Nếu M[j] nhỏ hơn hoặc bằng M[i], thì các phần tử được hoán đổi vị trí bằng cách sử dụng biến tạm tam. Cụ thể, lệnh Tam:= M[i]; M[i]:=M[j]; M[j]:=tam; được sử dụng để hoán đổi giá trị của M[i] và M[j].
  5. 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 đến n được đưa vào vị trí đúng sau phần tử M[i].
  6. 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.
  7. 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],';');.
  8. 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:

  1. Bắt đầu với một mảng chưa được sắp xếp.
  2. Đặt biến i từ 1 đến (n-1) (với n là số phần tử trong mảng).
  3. 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 đến n.
  4. 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.
  5. Tăng giá trị của i lên 1 và quay lại bước 3 cho đến khi i đạt đến (n-1).
  6. 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).