tailieunhanh - Bài giảng Kỹ thuật lập trình: Chương 3.3 - Trường Đại học Ngoại ngữ - Tin học TP.HCM

Bài giảng Kỹ thuật lập trình: Chương cung cấp cho người đọc những kiến thức như: Kỹ thuật sắp xếp; Thuật toán sắp xếp; kỹ thuật tìm kiếm; .Mời các bạn cùng tham khảo! | KỸ THUẬT LẬP TRÌNH CƠ BẢN Khoa Công nghệ thông tin Trường Đại học Ngoại ngữ - Tin học HUFLIT KỸ THUẬT SẮP XẾP Sắp xếp Sắp xếp sorting sắp xếp là tiến trình sắp xếp lại dữ liệu theo thứ tự nào đó Ví dụ 1 4 3 2 1 2 3 4 1 a 4 b 3 c 2 d 1 a 2 d 3 c 4 b Key Khóa key Một dữ liệu trong danh sách dữ liệu có thể có nhiều fields. Field có thể vài fields dùng để sắp xếp gọi là khóa key 3 Sắp xếp Chúng ta có thể sắp xếp Các số numbers Các từ các chuỗi words Các cặp pairs giá trị Thứ tự sắp xếp được sử dụng nhiều nhất Sắp xếp các số theo thứ tự Sắp xếp các chuỗi theo thứ tự alphabet thứ tự từ điển Chúng ta xét hình thức đơn giản nhất sắp xếp dãy số nguyên 4 Sắp xếp Bài toán sắp xếp Cho mảng có số nguyên 1 2 . Hãy sắp xếp các phần tử theo thứ tự tăng dần 1 2 Mảng trước khi sắp xếp 1 4 3 2 8 9 4 6 Mảng đã được sắp xếp 1 2 3 4 4 6 8 9 5 Sắp xếp Tại sao phải sắp xếp dữ liệu Giúp tìm kiếm search nhanh hơn Giúp trộn merge các danh sách với nhau nhanh hơn Sorting có thể coi như là công cụ thiết kế thuật toán 6 Thuật toán sắp xếp Các lớp thuật toán sắp xếp tùy đặc điểm dữ liệu Thuật toán 2 Thuật toán . log Thuật toán Ba thuật toán cơ bản Interchange sort Selection sort 2 Quick sort sắp xếp nhanh . log Counting sort Distribution sort 7 Interchange sort Ý tưởng interchange sort Xét từng phần tử từ trái sang phải Với phần tử so sánh với các phần tử đứng sau Nếu gt thì Hoán vị với 8 Interchange sort Interchange sort Lần lặp 1 1 2 3 4 4 6 8 9 1 4 3 2 8 9 4 6 1 4 3 2 8 9 4 6 9 Interchange sort Interchange sort Lần lặp 2 1 4 3 2 8 9 4 6 1 4 3 2 8 9 4 6 10 Interchange sort Interchange sort Lần lặp 2 1 4 3 2 8 9 4 6 1 3 4 2 8 9 4 6 1 2 4 3 8 9 4 6 1 2 4 3 8 9 4 6 11 Interchange sort Interchange sort Lần lặp 3 1 2 4 3 8 9 4 6 1 2 4 3 8 9 4 6 12 Interchange sort Interchange sort Lần lặp 3 1 2 4 3 8 9 4 6 1 2 3 4 8 9 4 6 13 Interchange sort Interchange sort Lần lặp 4 1 2 3 4 8 9 4 6 1 2 3 4 8 9 4 6 1 2 3 4 8 9 4 6 14 Interchange sort Interchange sort Lần lặp 5 1 2 3 4 8 9 4 6 1 2 3 4 8 9 4