Thuật toán sắp xếp bằng tráo đổi
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (595.53 KB, 17 trang )
THUẬT TOÁN SẮP XẾP
THUẬT TOÁN SẮP XẾP
BẰNG TRÁO ĐỔI
BẰNG TRÁO ĐỔI
Lê Anh Nhật
Lê Anh Nhật
Email: [email protected]
Email: [email protected]
2
1. Xác định bài toán
1. Xác định bài toán
Input
Dãy A gồm N số nguyên a
Dãy A gồm N số nguyên a
1
1
, a
, a
2
2
,, a
,, a
N
N
.
.
Dãy A được sắp xếp lại
Dãy A được sắp xếp lại
thành dãy không giảm.
thành dãy không giảm.
Output
3
2. Ý tưởng
2. Ý tưởng
•
Với mỗi cặp số hạng đứng liền kề
trong dãy, nếu số trước lớn hơn số
sau ta đổi chỗ chúng cho nhau.
•
Việc đó được lặp lại cho đến khi
không có sự đổi chỗ nào xảy ra
nữa.
?
4
3. Thuật toán liệt kê
3. Thuật toán liệt kê
Bước 1
Nhập N, các số hạng a
1
, a
2
,, a
N
;
Bước 2 M := N;
Bước 3
Nếu M<2 thì đưa ra dãy A đã được
sắp xếp, rồi kết thúc;
Bước 4 M := M-1; i := 0;
5
3. Thuật toán liệt kê
3. Thuật toán liệt kê
Bước 5 i := i + 1;
Bước 6 Nếu i > M thì quay lại bước 3;
Bước 7
Nếu a
i
> a
i+1
thì đổi a
i
và a
i+1
cho nhau;
Bước 8 Quay lại bước 5;
6
4. Thuật toán sơ đồ khối
4. Thuật toán sơ đồ khối
Nhập: N, a
1
, a
2
,, a
N
M := N
M < 2
S
M := M-1; i := 0;
Đưa dãy A ra
End.
Begin
Đ
i := i+1;
i > M
a
i
> a
i+1
Tráo đổi a
i
và a
i+1
Đ
S
S
Đ
7
5. Ví dụ mô phỏng
5. Ví dụ mô phỏng
6 2 5 3 7 8 10 7 12 4
Cho dãy số có 10 phần tử:
Sắp xếp dãy trên tăng dần theo thật toán tráo đổi?
8
5. Ví dụ mô phỏng
5. Ví dụ mô phỏng
6 2 5 3 7 8 10 7 12 4
M = 9;
2 65 6 63
7 10 4 12
9
5. Ví dụ mô phỏng
5. Ví dụ mô phỏng
M = 8;
2 5 3 6 7 8 7 10 4 123 5
7 8 4 10
10
5. Ví dụ mô phỏng
5. Ví dụ mô phỏng
M = 7;
2 3 5 6 7 7 8 4 10 124 8
11
5. Ví dụ mô phỏng
5. Ví dụ mô phỏng
M = 6;
2 3 5 6 7 7 4 8 10 124 7
12
5. Ví dụ mô phỏng
5. Ví dụ mô phỏng
M = 5;
2 3 5 6 7 4 7 8 10 124 7
13
5. Ví dụ mô phỏng
5. Ví dụ mô phỏng
M = 4;
2 3 5 6 4 7 7 8 10 124 6
14
5. Ví dụ mô phỏng
5. Ví dụ mô phỏng
M = 3;
2 3 5 4 6 7 7 8 10 124 5
15
5. Ví dụ mô phỏng
5. Ví dụ mô phỏng
M = 2;
2 3 4 5 6 7 7 8 10 12
16
5. Ví dụ mô phỏng
5. Ví dụ mô phỏng
M = 1;
2 3 4 5 6 7 7 8 10 12
Ta được dãy đã sắp xếp:
Kết thúc.
17
6. Bài tập
6. Bài tập
1.
1.
Cho dãy số có 13 số: 3, 6, 2, 5, 13, 21, 1, 9,
Cho dãy số có 13 số: 3, 6, 2, 5, 13, 21, 1, 9,
10, 14, 15, 2, 8.
10, 14, 15, 2, 8.
Áp dụng thuật toán trên để sắp xếp dãy trên
Áp dụng thuật toán trên để sắp xếp dãy trên
giảm dần?
giảm dần?
2.
2.
Từ thuật toán trên, sử dụng ngôn ngữ lập
Từ thuật toán trên, sử dụng ngôn ngữ lập
trình mà bạn biết để lập trình bài toán tổng
trình mà bạn biết để lập trình bài toán tổng
quát đó?
quát đó?
2. Ý tưởng2. Ý tưởngVới mỗi cặp số hạng đứng liền kềtrong dãy, nếu số trước lớn hơn sốsau ta đổi chỗ chúng cho nhau. Việc đó được lặp lại cho đến khikhông có sự đổi chỗ nào xảy ranữa. 3. Thuật toán liệt kê3. Thuật toán liệt kêBước 1N hập N, những số hạng a, a, , aBước 2 M : = N ; Bước 3N ếu M < 2 thì đưa ra dãy A đã đượcsắp xếp, rồi kết thúc ; Bước 4 M : = M-1 ; i : = 0 ; 3. Thuật toán liệt kê3. Thuật toán liệt kêBước 5 i : = i + 1 ; Bước 6 Nếu i > M thì quay lại bước 3 ; Bước 7N ếu a > ai + 1 thì đổi avà ai + 1 cho nhau ; Bước 8 Quay lại bước 5 ; 4. Thuật toán sơ đồ khối4. Thuật toán sơ đồ khốiNhập : N, a, a, , aM : = NM < 2M : = M-1 ; i : = 0 ; Đưa dãy A raEnd. Begini : = i + 1 ; i > M > ai + 1T ráo đổi avà ai + 15. Ví dụ mô phỏng5. Ví dụ mô phỏng6 2 5 3 7 8 10 7 12 4C ho dãy số có 10 thành phần : Sắp xếp dãy trên tăng dần theo thật toán tráo đổi ? 5. Ví dụ mô phỏng5. Ví dụ mô phỏng6 2 5 3 7 8 10 7 12 4M = 9 ; 2 65 6 637 10 4 125. Ví dụ mô phỏng5. Ví dụ mô phỏngM = 8 ; 2 5 3 6 7 8 7 10 4 123 57 8 4 10105. Ví dụ mô phỏng5. Ví dụ mô phỏngM = 7 ; 2 3 5 6 7 7 8 4 10 124 8115. Ví dụ mô phỏng5. Ví dụ mô phỏngM = 6 ; 2 3 5 6 7 7 4 8 10 124 7125. Ví dụ mô phỏng5. Ví dụ mô phỏngM = 5 ; 2 3 5 6 7 4 7 8 10 124 7135. Ví dụ mô phỏng5. Ví dụ mô phỏngM = 4 ; 2 3 5 6 4 7 7 8 10 124 6145. Ví dụ mô phỏng5. Ví dụ mô phỏngM = 3 ; 2 3 5 4 6 7 7 8 10 124 5155. Ví dụ mô phỏng5. Ví dụ mô phỏngM = 2 ; 2 3 4 5 6 7 7 8 10 12165. Ví dụ mô phỏng5. Ví dụ mô phỏngM = 1 ; 2 3 4 5 6 7 7 8 10 12T a được dãy đã sắp xếp : Kết thúc. 176. Bài tập6. Bài tập1. 1. Cho dãy số có 13 số : 3, 6, 2, 5, 13, 21, 1, 9, Cho dãy số có 13 số : 3, 6, 2, 5, 13, 21, 1, 9,10, 14, 15, 2, 8.10, 14, 15, 2, 8. Áp dụng thuật toán trên để sắp xếp dãy trênÁp dụng thuật toán trên để sắp xếp dãy trêngiảm dần ? giảm dần ? 2.2. Từ thuật toán trên, sử dụng ngôn từ lậpTừ thuật toán trên, sử dụng ngôn từ lậptrình mà bạn biết để lập trình bài toán tổngtrình mà bạn biết để lập trình bài toán tổngquát đó ? quát đó ?
