Thuật toán sắp xếp bằng tráo đổi
Chia sẻ bởi Vi Đình Nghĩa |
Ngày 01/05/2019 |
58
Chia sẻ tài liệu: Thuật toán sắp xếp bằng tráo đổi thuộc Power Point
Nội dung tài liệu:
Thuật toán sắp xếp bằng tráo đổi
Xác định bài toán:
INPUT: Dãy A gồm N số nguyên a1, a2,., aN.
OUTPUT: Dãy A được sắp xếp thành dãy không giảm.
ý tưởng: nếu có ai>ai+1 thì tráo đổi cho đến khi không còn sự tráo đổi nữa
? Với N = 6 và dãy A gồm 6 số hạng như sau :
? Lượt thứ nhất:
? Lượt thứ hai:
? Lượt thứ ba:
? Lượt thứ tư:
Mô phỏng thuật toán sắp xếp bằng tráo đổi
Liệt kê các bước
B1: Nhập N, các số hạng a1, a2,., aN;
B2: M ? N;
B3: Nếu M < 2 thì đưa ra dãy A đã sắp xếp rồi kết thúc;
B4: M ? M - 1; i ? 0;
B5: i ? i +1;
B6: Nếu i > M thì quay lại B3;
B7: Nếu ai > ai+1 thì tráo đổi ai và ai+1 cho nhau;
B8: Quay lại B5.
Đoạn chương trình trong Pascal
For M:=N downto 1 do
for i:=1 to M-1 do
if a[i]>a[i+1] then
begin
t:=a[i];
a[i]:=a[i+1];
a[i+1]:=t;
end;
Begin Kt:=false;
Kt:=true;
For M:=N downto 1 do
for i:=1 to M-1 do
if a[i]>a[i+1] then
begin
t:=a[i];
a[i]:=a[i+1];
a[i+1]:=t;
end;
If KT=false then break;
End;
Xác định bài toán:
INPUT: Dãy A gồm N số nguyên a1, a2,., aN.
OUTPUT: Dãy A được sắp xếp thành dãy không giảm.
ý tưởng: nếu có ai>ai+1 thì tráo đổi cho đến khi không còn sự tráo đổi nữa
? Với N = 6 và dãy A gồm 6 số hạng như sau :
? Lượt thứ nhất:
? Lượt thứ hai:
? Lượt thứ ba:
? Lượt thứ tư:
Mô phỏng thuật toán sắp xếp bằng tráo đổi
Liệt kê các bước
B1: Nhập N, các số hạng a1, a2,., aN;
B2: M ? N;
B3: Nếu M < 2 thì đưa ra dãy A đã sắp xếp rồi kết thúc;
B4: M ? M - 1; i ? 0;
B5: i ? i +1;
B6: Nếu i > M thì quay lại B3;
B7: Nếu ai > ai+1 thì tráo đổi ai và ai+1 cho nhau;
B8: Quay lại B5.
Đoạn chương trình trong Pascal
For M:=N downto 1 do
for i:=1 to M-1 do
if a[i]>a[i+1] then
begin
t:=a[i];
a[i]:=a[i+1];
a[i+1]:=t;
end;
Begin Kt:=false;
Kt:=true;
For M:=N downto 1 do
for i:=1 to M-1 do
if a[i]>a[i+1] then
begin
t:=a[i];
a[i]:=a[i+1];
a[i+1]:=t;
end;
If KT=false then break;
End;
* Một số tài liệu cũ có thể bị lỗi font khi hiển thị do dùng bộ mã không phải Unikey ...
Người chia sẻ: Vi Đình Nghĩa
Dung lượng: |
Lượt tài: 0
Loại file:
Nguồn : Chưa rõ
(Tài liệu chưa được thẩm định)