Bài 4 tiết 12- Bài toán sắp xếp

Lớp 10A7
Kính chào các thầy cô giáo tới dự giờ
Trả lời
ý tưởng tìm giá trị lớn nhất của dãy N số nguyên là:

Khởi tạo giá trị Max=a1

Lần lượt với i từ 2 đến N, so sánh giá trị số hạng ai với giá trị Max, nếu ai > Max thì Max nhận giá trị mới là ai
Kiểm tra bài cũ
Hãy nêu ý tưởng tìm giá trị lớn nhất của dãy N số nguyên a1,a2,.,aN?
Bài 4
Bài toán và thuật toán
(tiếp)
Bài toán sắp xếp
Hãy tìm cách sắp xếp học sinh đứng chào cờ (hình a) theo thứ tự thấp trước cao sau (hình b).
Hình a
Hình b
Cho dãy A gồm N số nguyên a1,a2,.,aN.
Cần sắp xếp các số hạng để A trở thành dãy
không giảm (tức là số hạng trước không lớn hơn
số hạng sau)

VD: Dãy A gồm các số nguyên: 3, 5, 9, 8, 1, 7, 3
Sau khi sắp xếp ta có dãy:
1, 3, 3, 5, 7, 8, 9
Bài toán sắp xếp
Thuật toán sắp xếp bằng tráo đổi (Exchange Sort)
OUTPUT: Dãy A được sắp xếp thành dãy không giảm.
Xác định bài toán:

INPUT: Dãy A gồm N số nguyên a1, a2,., aN.

ý 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ó sự đổi chỗ nào xảy ra nữa.
? Với N = 6 và dãy A gồm 6 số hạng như sau :
? Lượt thứ nhất:
? Lượt thứ hai:
? Lượt thứ ba:
? Lượt thứ tư:
Mô phỏng thuật toán sắp xếp bằng tráo đổi
Thuật toán
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.
Nhận xét
Qua thuật toán và qua ví dụ mô phỏng hãy đưa ra nhận xét
Sau mỗi lần đổi chỗ, giá trị lớn nhất của dãy A được chuyển dần về cuối dãy, sau lượt thứ nhất thì giá trị lớn nhất xếp đúng vị trí là ở cuối dãy. Tương tự sau lượt thứ 2, giá trị lớn thứ 2 được xếp đúng vị trí sát cuối.
Sau mỗi lượt có ít nhất 1 số hạng không còn tham gia vào quá trình đổi chỗ nữa ? sắp xếp nổi bọt (Bubble Sort).
Biến nguyên M thể hiện dãy sau khi được bỏ bớt phần tử cuối dãy, nó có giá trị khởi tạo là N, sau mỗi lượt M giảm 1 đơn vị cho đến khi M<2.
i là biến chỉ số có giá trị nguyên thay đổi từ 0 đến M+1
Cách 2
Vẽ sơ đồ khối
Hiểu ý tưởng thuật toán sắp xếp bằng tráo đổi

Trình bày thuật toán bằng 1 trong 2 cách

Mô phỏng được hoạt động của thuật toán
Củng cố
Hãy bổ sung những
chỗ thiếu
Nhập N và
a1, a2,..., aN
Đ
S
i >M?
Đ
Đổi chỗ ai và ai+1
S
Thuật toán sắp xếp dãy số không giảm
Làm lại bài tập ví dụ đã chữa, lấy thêm ví dụ khác tương tự

Bài 6: sgk T44
Cho N và dãy a1, a2,., aN, hãy sắp xếp dãy số đó thành dãy số không tăng (số hạng trước lớn hơn số hạng sau).

Đọc bài toán tìm kiếm và thuật toán tìm kiếm tuần tự để giờ sau chúng ta tìm hiểu
Bài tập về nhà
Bài học đã
KẾT THÚC
Thân ái chào các thầy cô và các em!