BÀI 14 THUẬT TOÁN SẮP XẾP TIN HỌC 7 -CTST

I. Thuật toán sắp xếp nổi bọt

1. Mục tiêu bài học:

Học sinh hiểu và mô tả được thuật toán sắp xếp đơn giản (chủ yếu là thuật toán sắp xếp nổi bọt – Bubble Sort).
Biết biểu diễn thuật toán bằng sơ đồ khối hoặc mô tả bằng ngôn ngữ tự nhiên.

2. Thuật toán sắp xếp nổi bọt (Bubble Sort):

2.1 Ý tưởng chính:

So sánh cặp phần tử kề nhau và hoán đổi nếu chúng không đúng thứ tự. Lặp lại nhiều lượt như vậy cho đến khi dãy được sắp xếp.

Mô tả bằng ngôn ngữ tự nhiên:
Xét từng phần tử trong dãy từ đầu đến phần tử kế cuối.
Tại mỗi bước, so sánh phần tử hiện tại với phần tử ngay sau nó:
Nếu phần tử hiện tại lớn hơn phần tử sau → hoán đổi chúng.
Sau mỗi lượt, phần tử lớn nhất sẽ "nổi" lên cuối dãy chưa được sắp.
Giảm phạm vi xét dãy đi 1 và lặp lại.

Kết thúc khi không còn cần hoán đổi nào nữa (dãy đã được sắp).

2.2 Ví dụ cho dãy số ban đầu: 5, 2, 9, 1

Lần 1:

So sánh 5 và 2 → đổi → 2, 5, 9, 1
So sánh 5 và 9 → không đổi
So sánh 9 và 1 → đổi → 2, 5, 1, 9

Lần 2:

So sánh 2 và 5 → không đổi
So sánh 5 và 1 → đổi → 2, 1, 5, 9

Lần 3:

So sánh 2 và 1 → đổi → 1, 2, 5, 9

Dãy đã sắp tăng dần: 1, 2, 5, 9

3. Minh Họa:

Nhằm giúp học sinh hiểu sâu về về thuật toán sắp xếp nổi bọt. Chương trình mô phỏng thuật toán Bubble Sort sau sẽ giúp các em có cách nhìn tổng quan về thuật toán.

Bước 1: Học sinh chọn số phần tử cần sắp xếp,
Bước 2: Chọn tốc độ sắp xếp nhanh hoặc chậm thông qua thanh trượt.
Bước 3: Sau đó chọn Sắp xếp tự động hoặc từng bước

Mô phỏng Bubble Sort nâng cao

Mô phỏng thuật toán Bubble Sort

Số phần tử (2–20):

Tốc độ (ms): 1000 ms

Hãy tạo dãy số để bắt đầu.

Trang chủ Thuật toán

thuật toán Sắp xếp Tin Học 7