Lecturer: PhD. Ngo Huu Phuc
Tel: 0438 326 077
Mob: 098 5696 580
Email: ngohuuphuc76@gmail.com
Cấu trúc dữ liệu và giải thuật
Bài 5. Phương pháp sắp xếp đơn giản
Ngo Huu Phuc, Le Quy Don Technical University
1
Bài 5: Các phương pháp sắp xếp đơn giản
Nội dung:
6.1. Khái niệm và vai trò của sắp xếp (13)
6.2. Sắp xếp chèn (6)
6.3. Sắp xếp chọn (4)
6.4. Sắp xếp nổi bọt (4)
Tham khảo:
1. Lecture 16 Introduction to Sorting.htm
2. Data Structures and Algorithms Sorting.htm
3. Tham khảo bài giảng của TS Nguyễn Nam Hồng
Ngo Huu Phuc, Le Quy Don Technical University
2
5.1. Khái niệm và vai trò của sắp xếp
5.1.1. Các thuật toán sắp xếp.
5.1.2. Vai trò của sắp xếp.
5.1.3. Các vấn đề của sắp xếp.
5.1.4. Một số ứng dụng của sắp xếp.
5.1.5. Ý tưởng sắp xếp và phương pháp thực hiện.
5.1.6. Phân tích hiệu quả của giải thuật sắp xếp.
Ngo Huu Phuc, Le Quy Don Technical University
3
5.1.1. Các thuật toán sắp xếp (1/2)
Thế nào là sắp xếp?
Đưa một dãy các đối tượng về dạng thứ bậc nào đó.
Giải thuật sắp xếp dựa trên sự so sánh nào đó.
Việc sắp xếp chỉ dựa trên phép toán so sánh.
Các phép toán cơ bản của sắp xếp.
So sánh.
Tráo đổi giữa các phần tử.
Ngo Huu Phuc, Le Quy Don Technical University
4
5.1.1. Các thuật toán sắp xếp (1/2)
Quy ước.
Phương pháp sắp xếp của chương này là sắp xếp
trong.
Các giải thuật có thể thay thế cho nhau được.
Mỗi mảng có một số phần tử.
Thành phần để xem xét trong sắp xếp có thể so
sánh được.
N là số phần tử cần sắp xếp.
Ngo Huu Phuc, Le Quy Don Technical University
5