Bài giảng Kỹ thuật lập trình C: Chương 7 - ThS. Trần Quang Hải Bằng

Trong chương 7 Các thuật toán sắp xếp nằm trong bài giảng kỹ thuật lập trình C nhằm trình bày về các nội dung chính: bài toán sắp xếp, các giải thuật sắp xếp, đổi chỗ trực tiếp, các giải thuật sắp xếp, chọn trực tiếp, chèn trực tiếp.
Nội dung trích xuất từ tài liệu:
Bài giảng Kỹ thuật lập trình C: Chương 7 - ThS. Trần Quang Hải Bằng 04/2010 Bài toán s p x p • Cho t p N ph n t , m i ph n t có m t s thu c tính K THU T L P TRÌNH C • D a vào 1 (ho c vài) thu c tính c a các ph n t ñ s p x p l i chúng theo tr t t m i. Chương 7: Các thu t toán s p x pbangtqh@hotmail.com bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 2 04/2010 04/2010Bài toán s p x p Các gi i thu t s p x p• G m 2 bài toán con: • S p x p đ i ch tr c ti p - Interchange Sort – D a theo khoá s p x p đ nh v l i th t các • S p x p ch n tr c ti p – Selection Sort ph n t • S p x p chèn tr c ti p – Insertion Sort – Chuy n các ph n t c n s p v v trí m i. • S p x p n i b t – Buble Sort • S p x p n i b t c i ti n - Shaker Sort• Hai thao tác cơ b n • Shell sort – So sánh • Heap sort – Gán • Quick sort • Merge sortbangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 3 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 4 04/2010 04/2010Đ i ch tr c ti p – Interchange Sort Đ i ch tr c ti p – Interchange Sort• Khái ni m ngh ch th : • Tìm t t c ngh ch th , tri t tiêu chúng b ng – Xét m t m ng các s a0, a1, . an. cách hoán v 2 ph n t tương ng trong – N u có i aj, thì ta g i đó là m t ngh ch ngh ch th th .• M ng chưa s p x p s có ngh ch th• M ng đã có th t s không ch a ngh ch thbangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 5 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 6 04/2010 04/2010 Đ i ch tr c ti p – Interchange Sort Đ i ch tr c ti p – Interchange Sort • Bư c 1 : i = 1; // b t đ u t ñ u dãy • Cho dãy s a: • Bư c 2 : j = i+1; //tìm các ph n t a[j] < a[i], j>i 12 2 8 5 1 6 4 15 • Bư c 3 : Trong khi j < N th c hi n N u a[j] 04/2010 04/2010Đ i ch tr c ti p – Interchange Sort Đ i ch tr c ti p – Interchange Sortbangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 9 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 10 04/2010 04/2010Đ i ch tr c ti p – Interchange Sort Đ i ch tr c ti p – Interchange Sortbangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 11 bangtqh@hotmail.com K thu t l p trình C - Thu t toán s p x p 12 04/2010 04/2010Đ i ch tr c ti p – Interchange Sort Interchange Sort - K t qu ...