Bài giảng Tin học Lớp 7 KNTT - Bài 16: Thuật toán sắp xếp

Môn: Tin học 7 
BÀI 16. THUẬT TOÁN SẮP XẾP 
BÀI 
16 
3. LUYỆN TẬP 
1. KHỞI ĐỘNG 
4. VẬN DỤNG 
NỘI DUNG BÀI HỌC 
2.1. Thuật toán sắp xếp nổi bọt 
 2.2. Thuật toán sắp xếp chọn 
2. HÌNH THÀNH KIẾN THỨC 
 2.2. Chia bài toán thành những bài toán nhỏ hơn 
Khởi 
động 
Có hai chất lỏng khác nhau là xanh và đỏ, lần lượt được chứa trong hai chiếc cốc A và B 
(Hình 16.1a). Chúng ta cần đổi chỗ hai chất lỏng này, sao cho cốc A đựng chất lỏng màu đỏ, còn cốc B đựng chất lỏng màu xanh. Để thực hiện công việc này, chúng ta sử dụng thêm một chiếc cốc thứ ba (cốc C) không đựng gì. Em hãy quan sát Hình 16.1b, Hình 16.1c, Hình 16.1d để biết cách thực hiện. 
HÌNH THÀNH KIẾN THỨC 
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 
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. 
Xét vị trí đầu tiên, vòng lặp thứ nhất thực hiện nh ư sau: 
Xét vị trí thứ hai: 
Sau vòng lặp thứ ba, không có bất kì sự hoán đổi nào được thực hiện nữa nên thuật toán dừng lại. Danh sách được sắp xếp theo đúng thứ tự yêu cầu. 
Xét vị trí thứ ba : 
MÔ PHỎNG THUẬT TOÁN 
HOẠT ĐỘNG NHÓM:  HOÀN THÀNH PHIẾU HỌC TẬP SỐ 1 
Hãy điền vào các ô còn trống để thể hiện quá trình sắp xếp một dãy số theo thứ tự tăng dần bằng thuật toán sắp xếp nổi bọt. 
3 
5 
4 
1 
2 
3 
5 
1 
4 
2 
3 
1 
5 
4 
2 
1 
3 
5 
4 
2 
1 
3 
5 
2 
4 
1 
3 
2 
5 
4 
1 
2 
3 
5 
4 
1 
2 
3 
4 
5 
1 
2 
3 
4 
5 
1 
2 
3 
4 
5 
Mô tả thuật toán tìm kiếm tuần tự bằng ngôn ngữ tự nhiên: 
Sắp xếp dãy số theo thứ tự tăng bằng thuật toán sắp xếp nổi bọt. 
1. Với phần tử đầu tiên, em thực hiện một vòng lặp như sau: 
1.1. So sánh hai phần tử đứng cạnh nhau theo thứ tự từ cuối dãy lên phần tử đầu tiên. 
1.2. Nếu phần tử đứng sau nhỏ hơn phần tử đứng trước thì đổi chỗ chúng cho 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 tiên. 
2. Với phần tử thứ hai, em thực hiện một vòng lặp tương tự như trên. 
2.1. So sánh hai phần tử đứng cạnh nhau theo thứ tự từ cuối dãy ngược lên phần tử 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 nhau. 
2.3. Cuối vòng lặp em sẽ nhận được dãy số với phần tử nhỏ thứ nhì nổi lên vị trí thứ hai. 
3. Tương tự như trên với các phần tử thứ ba, thứ tư,... đến phần tử 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. 
	 Sắp xếp nổi bọt là thuật toán sắp xếp được thực hiện bằng cá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ự. 
	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ự. 
C 
TRÒ CHƠI: “CÙNG NHAU SẮP XẾP” 
LUẬT CHƠI 
	Chia lớp thành 2 đội; mỗi đội chọn ra 4 bạn xếp thành 2 hàng chơi tiếp sức. Sử dụng thuật toán sắp xếp nổi bọt 
	Bạn thứ 1 ghi lên bảng bước 1 của thuật toán xong quay về rồi xuống đứng cuối hàng, bạn thứ 2 ghi lên bảng bước 2 của thuật toán (có thể sửa của các bạn phía trước) xong quay về rồi xuống đứng cuối hàng Tiến hành đến khi hoàn thành thuật toán hoặc đến khi hết thời gian 2 phút. 
TRÒ CHƠI: “CÙNG NHAU SẮP XẾP” 
3 
2 
4 
1 
5 
1 
2 
3 
4 
5 
3 
2 
1 
4 
5 
2 
3 
4 
1 
5 
3 
1 
2 
4 
5 
1 
3 
4 
2 
5 
1 
3 
2 
4 
5 
1 
2 
4 
3 
5 
1 
2 
3 
4 
5 
1 
2 
3 
4 
5 
VẬN DỤNG 
	Em hãy ghi lại kết quả điểm học tập môn Tin học của các bạn trong tổ. Thực hiện thuật toán sắp xếp nổi bọt để sắp xếp điểm theo thứ tự giảm dần. Dựa trên kết quả sắp xếp, hãy cho biết danh sách tên các bạn tương ứng theo kết quả sắp xếp đó. 
LOVE 
L 
L 
L 
L 
PIRCE 
G 
S 
T 
H 
TẠM BIỆT VÀ HẸN GẶP LẠI