ề
CĐ

Về kiến thức:
-Giải thích được một vài
thuật toán sắp xếp cơ bản.
-Biểu diễn và mô phỏng
được hoạt động của thuật
toán sắp xếp với bộ dữ liệu
đầu vào có kích thước nhỏ.
-Nêu được ý nghĩa của việc
chia một bài toán thành
những bài toán nhỏ hơn.

 Tin 7

Về năng lực:
2.1. Năng lực chung
-Năng lực tự chủ, tự học: Học sinh chủ động và tích cực thực hiện
nhiệm vụ học tập; vận dụng được những kiến thức, kĩ năng đã học để
hoàn thành nhiệm vụ.
-Năng lực giao tiếp và hợp tác: HS có khả năng hoạt động nhóm để
hoàn thành các nhiệm vụ học tập.
-Năng lực giải quyết vấn đề và sáng tạo: HS đưa ra thêm một số ví dụ
về thuật toán.
2.2. Năng lực Tin học
-Bước đầu hình thành quan niệm về giá trị của thông tin trong việc tổ
chức dữ liệu có trật tự.
-Hình thành tư duy mô hình hóa trong việc tổ chức và tìm kiếm dữ liệu
với sự trợ giúp của máy tính.

 Tin 7

ề
CĐ

NỘI
DUNG
TRỌNG
TÂM

1 Thuật toán sắp xếp nổi bọt
2 Thuật toán sắp xếp chọn
3 Chia bài toán thành những bài toán nhỏ hơn.

KHÁM
PHÁ

HOẠT ĐỘNG
1. Thuật toán sắp xếp nổi
bọt.

1. Thuật toán sắp xếp nổi bọt.
*Máy tính thường xuyên phải thực hiện thuật toán sắp xếp
khi người sử dụng yêu cầu. Có nhiều thuật toán sắp xếp
khác nhau. Một trong số đó là thuật toán sắp xếp nổi bọt.

*Giả sử ta cần phải sắp xếp dãy các số 4, 2, 3, 1 để thu
được dãy có thứ tự tăng dần. Thuật toán sắp xếp nổi
bọt xét từng vị trí từ đầu đến cuối dãy. Tại mỗi vị trí
được xét, thuật toán tìm phần tử nhỏ nhất trong những
phần tử phía sau để đưa vào vị trí đó. Việc này được
thực hiện bằng một vòng lặp, so sánh từng cặp phần tử
cạnh nhau và hoán đổi chúng nếu số ở phía sau nhỏ
hơn. Các bước thực hiện được mô tả trong Hình 16.2,
Hình 16.3, Hình 16.4. Việc hoán đổi được thực hiện
giống như việc hoán đổi ở Hoạt động khởi động.

 Tin 7

ề
CĐ

1. Thuật toán sắp xếp nổi bọt.
*Xét vị trí đầu tiên, vòng lặp thứ nhất thực hiện như sau:
DS đầu vào 4

2 3 1
Vòng lặp 1
4? 2? 1? ?3
4? 1? 2? ?3
1? 4? 2? 3?

Hoán đổi
1
2
3
4Kết thúc vòng 1

ề
CĐ

1. Thuật toán sắp xếp nổi bọt.
*Xét vị trí thứ hai, vòng lặp thứ hai thực hiện như sau:
DS vòng 1 4 2 3
lặp 1
Hoán đổi
Vòng lặp 2
1
?1 2? ?4 ?3
2
3Kết thúc vòng 2
4

 Tin 7

ề
CĐ

1. Thuật toán sắp xếp nổi bọt.
*Xét vị trí thứ ba, vòng lặp thứ ba thực hiện như sau:
DS vòng 1 2 4 3
lặp 2
Hoán đổi
Vòng lặp 3
1
?1 ?2 ?3 ?4
2
Kết thúc
3 vòng lặp 3. Vì đã
đến vị trí trước vị trí cuối
4
cùng nên dừng vòng lặp.

 Tin 7

Thuật toán sắp xếp nổi bọt
Nghiên cứu và thảo luận
Mô tả thuật toán sắp xếp nổi bọt bằng ngôn ngữ tự nhiên: (SGK trang 80)
-B1.Với vị trí đầu tiên, em thực hiện một vòng lặp như sau:
Em
1.1.So sánh hai phần tử đứng cạnh nhau theo thứ tự từ cuối dãy lên vị trí đầu tiên
hãy mô 1.2.Nếu phần tử đứng sau nhỏ hơn phần tử đứng trước thì đổi chỗ chúng cho
tả thuật nhau.
1.3.Cuối vòng lặp em sẽ nhận được dãy số với phần tử nhỏ nhất nổi lên vị trí đầu
toán
tiên.
sắp xếp -B2.Với vị trí thứ hai, em thực hiện một vòng lặp tương tự như trên.
?
nổi bọt 2.1.So sánh hai phần tử đứng cạnh nhau theo thứ tự từ cuối dãy lên vị trí thứ hai.
2.2.Nếu phần tử đứng sau nhỏ hơn phần tử đứng trước thì đổi chỗ chúng cho
bằng
nhau.
ngôn
2.3.Cuối vòng lặp em sẽ nhận được dãy số với phần tử nhỏ thứ nhì lên lên vị trí
ngữ tự thứ hai.
nhiên? -B3.Tương tư như trên các vị trí thứ ba, thứ tư,… đến vị trí trước vị trí cuối cùng.
-B4.Kết thúc, em sẽ nhận được dãy số đã được sắp xếp theo thứ tự từ nhỏ đến
lớn.

ề
CĐ

 Tin 7

1. Thuật toán sắp xếp nổi bọt.
Thuật toán sắp xếp nổi bọt
Nghiên cứu và thảo luận
Em hãy thực hiện thuật toán sắp xếp nổi bọt để sắp xếp 5 số sau đây
theo thứ tự tăng dần
3 5 4 1
2

 Tin 7

ề
CĐ

1. Thuật toán sắp xếp nổi bọt.
*Xét vị trí đầu tiên, vòng lặp thứ nhất thực hiện như sau:
DS đầu vào 3

Hoán đổi
1
2
3
4

5 4 1 2
Vòng lặp 1
?3 ?5 1? ?4 2?
?3 ?1 5? ?4 2?
1? ?3 ?5 4? ?2

Kết thúc vòng 1

 Tin 7

ề
CĐ

1. Thuật toán sắp xếp nổi bọt.
*Xét vị trí thứ hai, vòng lặp thứ hai thực hiện như sau:
DS vòng 1

Hoán đổi
1
2
3
4

1

3 5 4
Vòng lặp 2
?1 ?3 ?5 ?2
?1 ?3 ?2 ?5
?1 ?2 ?3 ?5

2
Kết thúc vòng 2

?4
?4
4?

 Tin 7

ề
CĐ

1. Thuật toán sắp xếp nổi bọt.
*Xét vị trí thứ ba, vòng lặp thứ ba thực hiện như sau:
DS vòng 2

Hoán đổi
1
2
3
4

1

2 3 5
Vòng lặp 3
?1 ?2 ?3 4?

4
5?

Kết thúc vòng 3.

 Tin 7

ề
CĐ

1. Thuật toán sắp xếp nổi bọt.
*Xét vị trí thứ tư, vòng lặp thứ tư thực hiện như sau:
DS vòng 4

Hoán đổi
1
2
3
4

1

2 3 4
Vòng lặp 4

5

Kết thúc vòng 4. Vì đã
đến vị trí trước vị trí
cuối cùng nên kết thúc
vòng lặp.

ề
CĐ

 Tin 7

1. Thuật toán sắp xếp nổi bọt.
Thuật toán sắp xếp nổi bọt
Nghiên cứu và thảo luận
Sắp xếp nổi bọt: Nổi bọt là thuật toán sắp
Thế nào là thuật toán xếp được thực hiện bằng cách hoán đổi
?
sắp xếp nổi bọt?
nhiều lần các phần tử liền kề nếu giá trị của
chúng không đúng thứ tự.

Bài tập
Thuật toán sắp xếp nổi bọt sắp xếp danh sách bằng cách:
Chọn phần tử có giá trị bé nhất đặt vào đầu danh sách.
Chọn phần tử có giá trị lớn nhất đặt vào đầu danh sách.
Hoán đổi nhiều lần các phần tử liền kề nếu giá trị của
chúng không đúng thứ tự.
Chèn phần tử vào vị trí thích hợp để đảm bảo
danh sách sắp xếp theo đúng thứ tự.

HOẠT ĐỘNG
2. Thuật toán sắp xếp chọn.

2. Thuật toán sắp xếp chọn.
*Giống thuật toán sắp xếp nổi
bọt, thuật toán sắp xếp chọn
cũng xét từng vị trí và đưa phần
tử nhỏ nhất trong những phần tử
phía sau vào vị trí đó. Tuy nhiên
việc này được thực hiện bằng
cách so sánh trực tiếp phần tử ở
vị trí được xét với những phần
tử ở phía sau nó và hoán đổi nếu
phần tử phía sau nhỏ hơn. Các
bước thực hiện được minh hoạ
trong Hình 16.5.

Mô tả thuật toán sắp xếp chọn bằng ngôn ngữ tự nhiên: (SGK trang 81)
Em hãy
mô tả
thuật
toán
sắp xếp
chọn
bằng
ngôn
ngữ tự
nhiên?

-B1. Với vị trí đầu tiên, em thực hiện một vòng lặp như sau:
1.1. So sánh từng phần tử (kể từ vị trí thứ hai đến vị trí cuối cùng) với phần tử tại
vị trí đầu tiên.
1.2. Nếu phần tử được xét nhỏ hơn phần tử tại vị trí đầu tiên thì hoán đổi nó với
phần tử tại vị trí đầu tiên.
1.3. Cuối vòng lặp, em sẽ nhận được dãy số với phần tử nhỏ nhất được đưa về vị
trí đầu tiên.
-B2. Với vị trí thứ hai, em thực hiện một vòng lặp tương tự như trên.
?
2.1.So sánh từng phần tử (kể từ vị trí thứ ba đến vị trí cuối cùng) với phần tử thứ
hai.
2.2. Nếu phần tử được xét nhỏ hơn phần tử tại vị trí thứ hai thì hoán đổi nó với
phần tử tại vị trí thứ hai.
2.3. Cuối vòng lặp, em sẽ nhận được dãy số với phần tử nhỏ thứ nhì được đưa về
vị trí thứ hai.
3. Tương tự như trên với các phần tử thứ ba, thứ tư,... đến vị trí trước phần tử cuối
cùng.
4. Kết thúc, em sẽ nhận được dãy số đã được sắp xếp theo thứ tự từ nhỏ đến lớn.

ề
CĐ

 Tin 7

2. Thuật toán sắp xếp chọn.
Sắp xếp chọn
Nghiên cứu và thảo luận
Em hãy thực hiện thuật toán sắp xếp chọn để sắp xếp 5 số sau đây
theo thứ tự tăng dần
41 15 17 32 18

 Tin 7

ề
CĐ

2. Thuật toán sắp xếp chọn.
*Xét vị trí đầu tiên, vòng lặp thứ nhất thực hiện như sau:
DS đầu vào 41 15 17 32 18

Hoán đổi
Vòng lặp 1
1
15
? 32
? 41
? 17
? 18
?
2
3
4

Kết thúc vòng 1

 Tin 7

ề
CĐ

2. Thuật toán sắp xếp chọn.
*Xét vị trí thứ hai, vòng lặp thứ hai thực hiện như sau:
DS vòng 1 15 41 17 32 18

Hoán đổi
Vòng lặp 2
? 32
1
15
? 17
? 41
? 18
?
2
3
4

Kết thúc vòng 2

 Tin 7

ề
CĐ

2. Thuật toán sắp xếp chọn.
*Xét vị trí thứ ba, vòng lặp thứ ba thực hiện như sau:
DS vòng 2 15 17 41 32 18

Hoán đổi
Vòng lặp 3
1
15
? 41
? 17
? 32
? 18
?
2
15
? 41
? 32
?
? 17
? 18
3
4

Kết thúc vòng 3

 Tin 7

ề
CĐ

2. Thuật toán sắp xếp chọn.
*Xét vị trí thứ tư, vòng lặp thứ tư thực hiện như sau:
DS vòng 3 15 17 18 41 32

Hoán đổi
Vòng lặp 4
1
15
? 17
? 18
? 41
?
? 32
2
3
4

Kết thúc vòng 4.
Vì đã đến vị trí
trước vị trí cuối
cùng nên vòng lặp
kết thúc.

ề
CĐ

 Tin 7

2. Thuật toán sắp xếp chọn.
Thuật toán sắp xếp chọn
Nghiên cứu và thảo luận
Thuật toán sắp xếp chọn: xét từng vị trí từ
đầu đến cuối dãy, so sánh trực tiếp phần tử
?
Thế nào là thuật toán
ở vị trí được xét với những phần tử ở phía
sắp xếp chọn?
sau nó và hoán đổi nếu chúng chưa đúng
thứ tự.

HOẠT ĐỘNG
3. Chia bài toán thành
những bài toán nhỏ hơn.

3. Chia bài toán thành những bài toán nhỏ hơn.
*Trong quá trình thực hiện cả hai thuật toán sắp xếp nổi bọt và sắp xếp
chọn, ta đều thấy xuất hiện nhiều lần thuật toán đơn giản hơn: hoán đổi
giá trị hai phần tử. Như vậy, bài toán sắp xếp đã được giải quyết dựa trên
lời giải của bài toán nhỏ hơn là bài toán hoán đổi giá trị.
-Xem xét thuật toán tìm kiếm nhị phân ở bài học trước, ta cũng nhận thấy
thuật toán tìm kiếm nhị phân thực hiện chia bài toán thành những bài toán
nhỏ hơn. Trong đó, bài toán nhỏ hơn là một phần của bài toán ban đầu.
Cụ thể, ở mỗi lần lặp, thuật toán tìm kiếm nhị phân đã thu hẹp vùng tìm
kiếm chỉ còn một nửa.
-Một cách khái quát, để giải quyết một bài toán, chúng ta đã dựa trên lời
giải của bài toán nhỏ hơn. Việc chia một bài toán thành những bài toán
nhỏ hơn giúp việc giải bài toán đó dễ dàng hơn, đồng thời việc mô tả
thuật toán dễ hiểu và dễ thực hiện hơn.

ề
CĐ

 Tin 7

3. Chia bài toán thành những bài toán nhỏ hơn.
Nghiên cứu và thảo luận Chia bài toán thành những bài toán nhỏ hơn
Em hãy cho biết ý
Ý nghĩa: Chia một bài toán thành những
nghĩa của việc chia bài
bài toán nhỏ hơn giúp? thuật toán dễ hiểu và
toán thành những bài
dễ thực hiện hơn.
toán nhỏ hơn?

Bài tập
Tại sao chúng ta chia bài toán thành những bài toán nhỏ
hơn?
Để thay đổi đầu vào của bài toán.
Để thay đổi yêu cầu đầu ra của bài toán.
Để bài toán dễ giải quyết hơn.
Để bài toán khó giải quyết hơn.

LUYỆN TẬP

 Tin 7

ề
CĐ

Bài tập: Em hãy liệt kê các bước của thuật toán sắp xếp nổi bọt
để sắp xếp các số 3, 2, 4, 1, 5, theo thứ tự tăng dần.
*Xét vị trí đầu tiên, vòng lặp thứ nhất thực hiện như sau:
DS đầu vào 3

Hoán đổi
1
2
3
4

?3
3?
1?

2 4 1
Vòng lặp 1
2? 1? 4?
?1 2? 4?
3? 2? 4?

5
Kết thúc vòng 1
5?
5?
5?

 Tin 7

ề
CĐ

Bài tập: Em hãy liệt kê các bước của thuật toán sắp xếp nổi bọt
để sắp xếp các số 3, 2, 4, 1, 5, theo thứ tự tăng dần.
*Xét vị trí thứ hai, vòng lặp thứ hai thực hiện như sau:
DS vòng 1

Hoán đổi
1
2
3
4

1

3 2 4 5
Vòng lặp 2
1? 2? 3? 4? 5?

Kết thúc vòng 2

 Tin 7

ề
CĐ

Bài tập: Em hãy liệt kê các bước của thuật toán sắp xếp nổi bọt
để sắp xếp các số 3, 2, 4, 1, 5, theo thứ tự tăng dần.
*Xét vị trí thứ ba, vòng lặp thứ ba thực hiện như sau:
DS vòng 2

Hoán đổi
1
2
3
4

1

2 3 4 5
Vòng lặp 3

Kết thúc vòng 3

 Tin 7

ề
CĐ

Bài tập: Em hãy liệt kê các bước của thuật toán sắp xếp nổi bọt
để sắp xếp các số 3, 2, 4, 1, 5, theo thứ tự tăng dần.
*Xét vị trí thứ tư, vòng lặp thứ tư thực hiện như sau:
DS vòng 3

Hoán đổi
1
2
3
4

1

2 3 4 5
Vòng lặp 4

Kết thúc vòng 4.
Vì đã đến vị trí
trước vị trí cuối
cùng nên kết thúc
vòng lặp.

 Tin 7

ề
CĐ

Bài tập: Em hãy liệt kê các bước của thuật toán sắp xếp chọn để
sắp xếp các số 3, 2, 4, 1, 5 theo thứ tự tăng dần.
*Xét vị trí đầu tiên, vòng lặp thứ nhất thực hiện như sau:
DS đầu vào 3

Hoán đổi
1
2
3
4

2 4 1 5
Vòng lặp 1
?2 ?3 4? ?1 5?
?1 ?3 4? ?2 5?

Kết thúc vòng 1

 Tin 7

ề
CĐ

Bài tập: Em hãy liệt kê các bước của thuật toán sắp xếp chọn để
sắp xếp các số 3, 2, 4, 1, 5 theo thứ tự tăng dần.
*Xét vị trí thứ hai, vòng lặp thứ hai thực hiện như sau:
DS vòng 1

Hoán đổi
1
2
3
4

1

3 4 2 5
Vòng lặp 2
?1 2? 4? 3? 5?

Kết thúc vòng 2

 Tin 7

ề
CĐ

Bài tập: Em hãy liệt kê các bước của thuật toán sắp xếp chọn để
sắp xếp các số 3, 2, 4, 1, 5 theo thứ tự tăng dần.
*Xét vị trí thứ ba, vòng lặp thứ ba thực hiện như sau:
DS vòng 2

Hoán đổi
1
2
3
4

1

2 4 3 5
Vòng lặp 3
?1 2? 3? ?4 5?

Kết thúc vòng 3

 Tin 7

ề
CĐ

Bài tập: Em hãy liệt kê các bước của thuật toán sắp xếp chọn để
sắp xếp các số 3, 2, 4, 1, 5 theo thứ tự tăng dần.
*Xét vị trí thứ tư, vòng lặp thứ tư thực hiện như sau:
DS vòng 3

Hoán đổi
1
2
3
4

1

2 3 4 5
Vòng lặp 4

Kết thúc vòng 4.
Vì đã đến vị trí
trước vị trí cuối
cùng nên kết thúc
vòng lặp.

Bài tập
Sau vòng lặp thứ nhất của thuật toán sắp xếp chọn,
phương án nào đúng?
Phần tử có giá trị nhỏ nhất trong dãy được tìm thấy và đổi
chỗ cho phần tử đứng đầu dãy.
Phần tử có giá trị lớn nhất trong dãy được tìm thấy và đổi
chỗ cho phần tử đứng đầu dãy.
Các phần tử liền kề được hoán đổi.
Phần tử có giá trị nhỏ nhất sẽ đổi vị trí cho
phần tử cuối dãy.

Bài tập
Thuật toán sắp xếp nổi bọt sắp xếp danh sách bằng cách
nào?
Thay thế.
Thay đổi.
Hoán đổi.
Cả A, B và C.

Bài tập

Nếu sử dụng thuật toán sắp xếp chọn để sắp xếp dãy số
8, 22, 7, 19, 5 theo thứ tự tăng dần thì số lần thực hiện
thao tác hoán đổi giá trị trong vòng lặp thứ nhất là:

2
3
4
5

Bài tập
Trong thuật toán sắp xếp nổi bọt kết thúc khi nào?
Khi các phần tử đã nằm đúng thứ tự mong muốn.
Không còn bất kì cặp liền kề trái thứ tự mong muốn.
Khi đến vị trí trước vị trí cuối cùng.
Cả A, B và C.

Bài tập
Hoán đổi vị trí hai phần tử liên tiếp khi chúng không
đúng thứ tự là cách sắp xếp của thuật toán nào?
Nổi bọt.
Chọn.
Cả A, B đều đúng.
Cả A, B đều sai.

Bài tập

Tìm phần tử nhỏ nhất trong dãy và đổi chỗ phần tử này
với phần tử đầu tiên của dãy chưa được sắp xếp là ý
tưởng của thuật toán nào?

Nổi bọt.
Chọn.
Cả A, B đều đúng.
Cả A, B đều sai.

Bài tập
Trong thuật toán sắp xếp nổi bọt thì dấu hiệu để biết dãy
chưa sắp xếp xong là gì?
Vẫn còn cặp phần tử liền kề không đúng thứ tự mong
muốn.
Dãy chưa được sắp xếp tăng dần.
Dãy chưa được sắp xếp giảm dần.
Cả A, B và C.

Bài tập
Thuật toán sắp xếp nổi bọt sắp xếp danh sách bằng cách
hoán đổi các phần tử liền kề bao nhiêu lần?
Một lần.
Hai lần.
Mười lần.
Nhiều lần.

Bài tập
Thuật toán sắp xếp chọn xét từng vị trí phần tử từ:
Đầu đến cuối.
Cuối đến đầu.
Giữa đến đầu.
Giữa đến cuối.

Bài tập
Các nhiệm vụ để thực hiện việc sắp xếp gồm:
So sánh.
Đổi chỗ.
So sánh và đổi chỗ.
Đổi chỗ và xoá.