HI GUYS , WELCOME
TO LESSON TODAY'S
• TRƯỜNG THCS LÝ THƯỜNG KIỆT
• LỚP 7D – TỔ 1
•

GỒM 8 THÀNH VIÊN

CHỦ ĐỀ F: GIẢI QUYẾT VẤN ĐỀ VỚI SỰ TRỢ
GIÚP
CỦA MÁY TÍNH
Bài 3: SẮP XẾP CHỌN
- Gồm 3 phần
1.

Ý tưởng sắp xếp bằng cách chọn dần

2. Thuật toán sắp xếp chọn
3. Bài toán sắp xếp

VẬY SẮP XẾP CHỌN LÀ GÌ?
SẮP XẾP CHỌN là một thuật toán sắp xếp đơn giản, dựa trên những việc
so sánh tại chỗ. Chọn phần thử nhỏ nhất trong dãy n phần tử ban đầu ,
đưa phần thử này về vị trí đúng đầu tiên của dãy hiện hành. Sau đó
không quan tâm đến nó nữa, xem dãy hiện hành chỉ còn n-1 phần tử của
dãy ban đầu, bắt đầu từ vị trí thứ 2.

1.Ý TƯỞNG SẮP XẾP BẰNG CÁCH CHỌN DẦN
• Giả sử cần đổi chỗ các số hạng trong dãy số 55, 19, 42, 94, 18, 67 để
tạo ra được dãy có thứ tự giảm dần. Ý tưởng giải quyết bài toán này
được thể hiện qua các bước sau và được minh hoạ ở Hình 1

1.Ý TƯỞNG SẮP XẾP BẰNG CÁCH CHỌN DẦN
• Bước 1: Số lớn nhất trong dãy số (94) cần được chuyển về vị trí thứ nhất
trong dãy, do đó đổi chỗ 94 với 55 (hình 1). Sau bước này, vì 94 đã ở đúng
vị trí mong muốn nên tiếp theo chỉ cần đổi các số còn lại: 19, 42, 55, 18,
67.
• Bước 2: Tiếp tục lặp việc “Chọn lấy số lớn nhất trong dãy số còn lại và đổi
chỗ nó với số đứng đầu dãy này” cho đến khi hết dãy ban đầu

2.THUẬT TOÁN SẮP XẾP CHỌN

2.THUẬT TOÁN SẮP XẾP CHỌN
Các bước để tìm được số lớn nhất của một dãy số nằm ở vị trí nào
(Hình 3):
• Bước 1: Tạm ghi nhận vị trí của số lớn nhất là 1.
• Bước 2: So sánh a2 với số lớn nhất, nếu a2 lớn hơn thì ghi nhận lại vị trí
số lớn nhất là 2.
• Cứ tiếp tục như vậy, đến khi so sánh xong an với số lớn nhất và ghi
nhận lại vị trí của số lớn nhất ( nếu cần ) thì số lớn nhất chính là số lớn
nhất trong toàn bộ dãy và ta đã tìm được vị trí m của số lớn nhất trong
dãy

2.THUẬT TOÁN SẮP XẾP CHỌN

3.BÀI TOÁN SẮP XẾP
• Sắp xếp là bài toán cơ sở trong tin học. Duy trì dữ liệu được sắp xếp
đúng thứ tự sẽ làm giảm đáng kể thời gian tìm kiếm dữ liệu. Các bài
toán sắp xếp trong thực tế rất đa dạng. Khi phát biểu bài toán cần xác
định rõ:
1. Dãy đầu vào: Sắp xếp những gì?
2. Tiêu chí: Sắp xếp theo cái gì? Thứ tự tăng hay giảm dần?
Ví dụ: sắp xếp danh sách kết quả điểm kiểm tra môn Tin học theo thứ tự
từ cao xuống thấp là bài toán sắp xếp. Tiêu chí sắp xếp là điểm kiểm tra
theo thứ tự giảm dần.
• Trong thực tế, khi sắp xếp thủ công (không dùng đến máy tính), thuật
toán sắp xếp chọn thường được dùng.

THE END