Cấu trúc dữliệu và giải thuật
Đỗ Tuấn Anh
anhdt@it-hut.edu.vn
Nội dung
zChương 1 – Thiết kếvà phân tích (5 tiết)
zChương 2 – Giải thuật đệ quy (10 tiết)
zChương 3 – Mảng và danh sách (5 tiết)
zChương 4 – Ngăn xếp và hàng đợi (10 tiết)
zChương 5 – Cấu trúc cây (10 tiết)
zChương 8 – Tìm kiếm (5 tiết)
zChương 7 – Sắp xếp (10 tiết)
zChương 6 – Đồ thị(5 tiết)
zChương 9 – Sắp xếp và tìm kiếm ngoài (after)
Chương 7 – Sắp xếp
1. Đặt vấn đề
2. Ba phương pháp sắp xếp cơ bản
•Sắp xếp lựa chọn – Selection Sort
•Sắp xếp thêm dần – Insertion Sort
•Sắp xếp nổi bọt/đổi chỗ- Bubble Sort
3. Sắp xếp hòa nhập – Merge Sort
4. Sắp xếp nhanh/phân đoạn – Quick Sort
5. Sắp xếp vun đống – Heap Sort
1. Đặt vấn đề
Sắp xếplà các thuật toán bốtrí lại các phần tử
của một mảng A[n] theo một thứtựnhất định.
Việc sắp xếp được tiến hành dựa trên khóa
của phần tử. Ví dụ: danh mục điện thoại gồm:
Tên cơ quan, địa chỉ, số điện thoại.
Đơn giản bài toán:
-Khóa là các giá trịsố
-Phần tửchỉcó trường khóa, không có các
thành phần khác
-Sắp xếp theo thứtự tăng dần
2. Ba phương pháp sắp xếp cơ bản
zSắp xếp lựa chọn – Selection Sort
zSắp xếp thêm dần – Insertion Sort
zSắp xếp nổi bọt/đổi chỗ- Bubble Sort