Bài giảng Kỹ thuật lập trình - Một số thuật toán và kỹ thuật nâng cao cung cấp cho người học các kiến thức: Thuật toán sắp xếp, thuật toán số học, quy hoạch động, kỹ thuật cài đặt các thuật toán hay qui trình tổng quát, thuật ngữ và bài đọc thêm tiếng Anh. | Bài giảng Kỹ thuật lập trình: Một số thuật toán và kỹ thuật nâng cao - ThS. Đặng Bình Phương (ĐH Khoa học Tự nhiên) Kỹ thuật lập trình ThS. Đặng Bình Phương (dbphuong@) Thuật toán sắp xếp Thuật toán số học Quy hoạch động Kỹ thuật cài đặt các thuật toán hay qui trình tổng quát Thuật ngữ và bài đọc thêm tiếng Anh 2/27/2014 Khoa CNTT - ĐH Khoa học tự nhiên 2 • Sắp xếp là quá trình xử lý một danh sách các phần tử để đặt chúng theo một thứ tự theo yêu cầu nào đó • Ví dụ: danh sách trước khi sắp xếp: {1, 25, 6, 5, 2, 37, 40} Danh sách sau khi sắp xếp: {1, 2, 5, 6, 25, 37, 40} sắp xếp giúp cho việc tìm kiếm được nhanh hơn. • Khi khảo sát các bài toán sắp xếp, ta phải làm việc nhiều với khái niệm nghịch thế. 2/27/2014 Khoa CNTT - ĐH Khoa học tự nhiên 4 • Xét một mảng các số a0, a1, , an Nếu i aj thì ta gọi đó là một nghịch thế. • Nhận xét: – Mảng chưa sắp xếp sẽ có nhiều nghịch thế – Mảng đã sắp xếp không chứa nghịch thế – Việc sắp xếp mảng là nhằm tìm cách giảm số nghịch thế bằng cách hoán vị các cặp nghịch thế (ai, aj) 2/27/2014 Khoa CNTT - ĐH Khoa học tự nhiên 5 • Nhóm thuật toán đơn giản nhưng chi phí cao: – Selection sort (phương pháp chọn trực tiếp) – Insertion sort (phương pháp chèn trực tiếp) – Binary Insertion sort (phương pháp chèn trực tiếp, tìm kiếm nhị phân) – Interchange sort (phương pháp đổi chỗ trực tiếp) – Bubble sort (phương pháp “nổi bọt”) – Shaker sort (phương pháp “lắc”, cải tiến của “nổi bọt”) 2/27/2014 Khoa CNTT - ĐH Khoa học tự nhiên 6 • Nhóm thuật toán phức tạp nhưng hiệu quả hơn: – Shell sort – Heap sort (phương pháp
