1 of 8

BÀI 4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 4)

3. Một số ví dụ về thuật toán

a. Bài toán sắp xếp

2 of 8

BÀI TOÁN SẮP XẾP

Hãy tìm cách sắp xếp các học sinh đang chào cờ (hình a) theo thứ tự thấp trước đến cao sau (hình b)

Hình a

Hình b

3 of 8

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 sắp xếp thành dãy không giảm.

Ý 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 vị trí chúng cho nhau. Việc đó được lặp lại cho đến khi không còn có sự đổi chỗ nào xảy ra nữa.

4 of 8

☞ Với N = 6 và dãy A gồm 6 số hạng như sau:

3

5

9

8

1

7

☞ Lượt thứ nhất:

3

5

9

8

1

7

3

5

8

9

1

7

3

5

8

1

9

7

3

5

8

1

7

9

☞ Lượt thứ hai :

3

5

8

1

7

9

3

5

1

8

7

9

3

5

1

7

8

9

☞ Lượt thứ ba :

3

5

1

7

8

9

3

1

5

7

8

9

3

1

5

7

8

9

1

3

5

7

8

9

☞ Lượt thứ tư­:

Mô phỏng thuật toán sắp xếp bằng tráo đổi

5 of 8

Cách 1: 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.

6 of 8

a/ N=10;

  • Dãy A:

Thuật toán sắp xếp bằng tráo đổi

​

Bài tập áp dụng: Mô phỏng việc thực hiện thuật toán sắp xếp với các dãy số sau?�

3

10

10

43

12

19

18

41

5

81

b/ N=10;

  • Dãy A:

c/ N=10;

  • Dãy A:

d/ N=10;

  • Dãy A:

85

17

21

41

22

29

8

51

25

21

9

8

1

4

7

5

2

10

3

6

9

12

6

98

100

32

625

301

98

70

7 of 8

Nhập N và dãy

a1, a2,..., aN

M ← N

M < 2 ?

M ← M - 1; i ←0

i ← i + 1

i > M ?

ai > ai+1 ?

Tráo đổi

ai và ai+1

Đưa ra dãy A đã sắp xếp rồi kết thúc

Đ

Đ

Đ

S

S

S

Cách 2

Vẽ sơ đồ khối

8 of 8

Câu 1. Trong thuật toán sắp xếp :

a. Có khi nào M = 1 không?

b. Có thể không dùng biến M được không? Nếu được hãy mô tả thuật toán bằng một trong hai cách: liệt kê hoặc sơ đồ khối?

Câu 2. Trình bày thuật toán giải các bài toán sau: Hoán đổi giá trị của hai biến thực A và C.

BÀI TẬP VỀ NHÀ