Xem mẫu
CHƯƠNG 2.(TT)
GIẢI THUẬT SẮPXẾP
Võ Quang Hoàng Khang Email: vqhkhang@gmail.com
1
Mục tiêu
Nắm vững, minh họa và tính toán được các
phép gán (hoán vị) các giải thuật sắp xếp cơ
bản trên mảng một chiều
Cài đặt được các giải thuật bằng ngôn ngữ
C/C++
2
Khái niệm
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ự thỏa mãn một tiêu chí nào đó dựa trên nội dung thông tin lưu giữ tại mỗi phần tử.
Khái niệm nghịch thế
a1 a2 a3 a4 … … aN-2 aN-1 aN
Giả sử xét mảng có thứ tự tăng dần, nếu có iaj thì ta gọi đó là nghịch thế.
Mục tiêu của sắp xếp là khử các nghịch thế (bằng cách hoán vị)
3
Các giải thuật sắp xếp cơ bản
Đổi chổ trực tiếp – Interchange Sort Chọn trực tiếp – Selection Sort Chèn trực tiếp – Insertion Sort Nổi bọt – Bubble Sort
Quick Sort
Một số giải thuật khác - đọc thêm trong tài liệu
4
Đổi chổ trực tiếp – interchange sort
Ý tưởng
Ý tưởng chính của giải thuật là xuất phát từ đầu
dãy, tìm tất cả nghịch thế chứa phần tử này, triệt
tiêu chúng bằng cách đổi chỗ phần tử này với
phần tử tương ứng trong cặp nghịch thế. Lặp lại
xử lý trên với các phần tử tiếp theo trong dãy.
5
...
- tailieumienphi.vn
nguon tai.lieu . vn