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. | 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ự .
