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 3.3 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!
Nội dung trích xuất từ tài liệu:
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 KỸ THUẬT LẬP TRÌNH CƠ BẢN Khoa Công nghệ thông tinTrường Đại học Ngoại ngữ - Tin học TP.HCM (HUFLIT)KỸ THUẬT SẮP XẾPSắ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) 3Sắ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 4Sắ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 5Sắ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 6Thuậ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: ?(?) 7Interchange 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 ? ? > ? ? thì Hoán vị ? ? với ? ? 8Interchange 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 9Interchange sort• Interchange sort • Lần lặp 2 1 4 3 2 8 9 4 6 1 4 3 2 8 9 4 6 10Interchange 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 11Interchange sort• Interchange sort • Lần lặp 3 1 2 4 3 8 9 4 6 1 2 4 3 8 9 4 6 12Interchange sort• Interchange sort • Lần lặp 3 1 2 4 3 8 9 4 6 1 2 3 4 8 9 4 6 13Interchange 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 14Interchange sort• Interchange sort • Lần lặp 5 1 2 3 4 8 9 4 6 1 2 3 4 8 9 4 6 1 2 3 4 8 9 4 6 1 2 3 4 4 9 8 6 1 2 3 4 4 9 8 6 15Interchange sort• Interchange sort • Lần lặp 6 1 2 3 4 4 9 8 6 1 2 3 4 4 9 8 6 16Interchange sort• Interchange sort • Lần lặp 6 1 2 3 4 4 9 8 6 1 2 3 4 4 9 8 6 1 2 3 4 4 8 9 6 1 2 3 4 4 6 9 8 17Interchange sort• Interchange sort • Lần lặp 7 1 2 3 4 4 6 9 8 1 2 3 4 4 6 9 8 1 2 3 4 4 6 8 9 18Interchange sort• Chương trình void InterchangeSort(int[] a) { for (int i=0; iInterchange sort• Ưu điểm • Cài đặt nhanh • Cài đặt ít lỗi• Khuyết điểm • Chạy chậm khi số phần tử lớn• Khi nào nên sử dụng? • Thuật toán sắp xếp ...