Bài giảng Môn Tin học lớp 10 - Bài 4: Bài toán và thuật toán (tiếp)

 bµi 4:Bµi to¸n vµ thuËt to¸n (TiÕp) Tieát 13: Baøi toaùn saép xeáp Nhöõng vieäc haèng ngaøy lieân quan ñeán saép xeáp : Saép xeáp saùch vôû . Xeáp haøng chaøo côø . Saép xeáp teân hoïc sinh . Xeáp ñieåm trung bình cuûa hoïc sinh . . . . . . . Giôùi thieäu baøi toaùn saép xeá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 Giôùi thieäu baøi toaùn saép xeáp Ta xeùt baøi toaùn daïng ñôn giaûn sau : Cho daõyA goàm N soá nguyeân a1 , a2 , a3 , . . . , aN. Caàn saép xeáp caùc soá haïng ñeå daõy A trôû thaønh daõy khoâng giaûm (Töùc laø soá haïng tröôùc khoâng lôùn hôn soá haïng sau) Ví duï : daõy A coù 6 phaàn töû :15 ; 8 ; 12 ; 11 ; 12 ; 9;20 daõy sau khi saép xeáp: 8 ; 9 ; 11 ; 12 ; 12 ; 15;20 SẮP XẾP BẰNG TRÁO ĐỔI (Exchange Sort) Xác định bài toán INPUT : Số nguyên dương N và Dãy A gồm N số nguyên a1, a2,…,aN. OUTPUT : Dãy A được sắp xếp lại một dãy không giảm 15 8 12 11 13 9 Nhaän xeùt: Tieán haønh duyeät töø ñaàu daõy ñeán cuoái daõy vôùi hai soá ñöùng lieàn keà nhau neáu soá ñöùng tröôùc lôùn hôn soá ñöùng sau thì tieán haønh ñoåi choã. Sau moãi laàn ñoåi choã, Phaàn töû lôùn nhaát seõ chuyeån daàn veà cuoái daõy. Sau moät laàn duyeät, Phaàn töû lôùn nhaát seõ naèm ôû cuoái daõy. Vieäc ñoù laëp ñi laëp laïi cho ñeán khi moïi phaàn töû trong daõy ñeàu ñaõ xeáp ñuùng thöù töï Quan saùt vaø cho nhaän xeùt caùch saép xeáp treân 15 8 12 11 13 9 15 8 12 11 13 9 SẮP XẾP BẰNG TRÁO ĐỔI Ý 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 chỗ 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 . Dãy ban đầu Dãy sau khi sắp xếp Lượt thứ nhất Lượt thứ hai Lượt thứ ba Lượt thứ tư Lượt thứ năm Böôùc 1: Nhaäp N vaø caùc soá haïng a1 , a2 ,. . . , aN; Böôùc 2: M N; Böôùc 3: Neáu M M thì quay laïi böôùc 3; Böôùc 7: Neáu ai>ai+1 thì traùo ñoåi ai vaø ai+1 cho nhau; Böôùc 8: Quay laïi böôùc 5. B.1 : Nhập N và các số hạng a1, a2,…,aN; B.2 : M  N ; B.3 : Nếu M M thì quay lại bước 3; B.7 : Nếu ai > ai+1 thì tráo đổi ai và ai+1 cho nhau; B.8 : Quay lại bước 5. a) Cách liệt kê : b) Sơ đồ khối : Nhập N và a 1 a 2 , … , a N Đưa ra A Kết thúc M M ? a i > a i + 1 ? M ¬N Tráo đổi a i +1 và a i i ¬ i + 1 B . 1 B . 2 B . 3 B . 4 B . 5 B . 6 B . 7 B . 8 Đ S Đ S S Đ Lµm bµi6(TR44/SGK),1.33(Tr18/SBT), 1.38(Tr19/SBT). §äc tr­íc thuËt to¸n t×m kiÕm tuÇn tù Bài tập tương tự và gợi ý Quan sát mô phỏng trong việc hình thành ý tưởng sắp xếp mới từ sự kết hợp thuật toán tìm số lớn nhất và thuật toán sắp xếp bằng cách tráo đổi vừa học. Em hãy liệt kê các bước hoặc vẽ sơ đồ khối cho ý tưởng thuật toán này Ý tưởng : 	Mỗi lượt tìm phần tử lớn nhất trong số các 	phần tử chưa sắp xếp. Đổi chỗ phần tử này 	với phần tử cuối dãy (phần chưa sắp xếp) 	Việc này lặp lại nhiều lượt, cho đến khi dãy 	chỉ còn duy nhất 1 phần tử chưa sắp xếp. Mô phỏng thuật toán Dãy ban đầu Dãy sau khi sắp xếp 2 4 8 5 7