Cấu trúc dữliệu và Giải thuật
Đỗ Bích Diệp -Khoa CNTT - ĐHBKHN 1
Đỗ Bích Diệp - Khoa CNTT
CấutrúcdữliệuvàGiảithuật
Chương VI: Sắpxếp
7 2 ⏐9 4 →2 4 7 9
7 ⏐2 →2 7 9 ⏐4 →4 9
7 →72 →29 →94 →4
Đỗ Bích Diệp - Khoa CNTT
Chương VI: Sắpxếp
zNội dung
1. Bài toán sắpxếp
2. Ba phương pháp sắpxếpcơbản
1. Lựachọn, thêm dầnvàđổichỗ
2. Phân tích, đánh giá
3. Sắpxếpkiểu hòa nhập
4. Sắpxếp nhanh
5. Sắpxếpkiểuvunđống
6. Mộtsốphương pháp sắpxếpđặcbiệt
Cấu trúc dữliệu và Giải thuật
Đỗ Bích Diệp -Khoa CNTT - ĐHBKHN 2
Đỗ Bích Diệp - Khoa CNTT
Bài toán Sắpxếp
–Sắpxếplạimộttập các phầntửdữliệu theo chiều
tăng dầnhoặcgiảmdần
23 78 45 832 56
823 32 45 78 56
Đỗ Bích Diệp - Khoa CNTT
Bài toán Sắpxếp
–Khóa sắpxếp
zMộtbộphậncủabản ghi biểudiễnđốitượng đượcsắp
zKhóa sẽ đượcsửdụng để xác định thứtựsắpxếpbản ghi
trong mộttậpcácbảnghi
–Bảng khóa:
zSửdụng trong sắpxếpkhimuốnhạnchếviệcdichuyểncác
bảnghidữliệu
zMộttậpcácbản ghi chỉchứa hai trường
–Khóa: chứa khóa sắpxếp
–Link: Con trỏghi địachỉcủabản ghi đốitượng dữliệutương ứng
zThứtựcác bản ghi trong bảng khóa cho phép xác định thứtự
củacácbản ghi dữliệu
Cấu trúc dữliệu và Giải thuật
Đỗ Bích Diệp -Khoa CNTT - ĐHBKHN 3
Đỗ Bích Diệp - Khoa CNTT
Các loạithuậttoánSắpxếp
ExchangeSelectionInsertion
Internal External
Sorts
•Insertion
•Shell
• Selection
•Heap
• Bubble
•Quick
• Natural
• Balanced
• Polyphase
Đỗ Bích Diệp - Khoa CNTT
Bài toán Sắpxếp
–Các đặctrưng củathuật toán sắpxếp
zTính ổnđịnh củathuật toán sắpxếp
–Các phầntửcó cùng khóa sẽgiữnguyên thứtựtương
đốicủa chúng nhưtrướckhisắpxếp
zTính tạichỗ
–Thuật toán đòi hỏi không gian nhớphụlà hằng số(không
phụthuộcvàosốlượng phầntửtrong dãy cầnsắp)
78 845 832 56 8832 45 56 78
Cấu trúc dữliệu và Giải thuật
Đỗ Bích Diệp -Khoa CNTT - ĐHBKHN 4
Đỗ Bích Diệp - Khoa CNTT
Bài toán Sắpxếp
–Trong chương này, bài toán sắpxếpđượcđơn
giảnhóadướidạng nhưsau
zĐầu vào: Một dãy các sốnguyên a1, a2, …, an
zĐầura: Một hoán vịcủadãysốđãchotrongđó các giá
trịđượcsắpxếp theo chiềutăng dần
Đỗ Bích Diệp - Khoa CNTT
Ba phương pháp sắpxếpcơbản
1. Sắpxếpkiểulựachọn (Selection Sort)
2. Sắpxếpkiểu thêm dần (Insertion Sort)
3. Sắpxếpkiểuđổichỗ-Sắpxếpkiểunổibọt
(Buble Sort)
Cấu trúc dữliệu và Giải thuật
Đỗ Bích Diệp -Khoa CNTT - ĐHBKHN 5
Đỗ Bích Diệp - Khoa CNTT
Sắpxếpkiểulựachọn – Selection Sort
–Ý tưởng:
zTạimỗilượt, chọnphầntửnhỏnhấttrong sốcác phần
tửchưađượcsắp. Đưaphầntửđượcchọnvàovịtrí
đúng bằng phép đổichỗ.
zSau lượtthứi (i = 1..n-1) , dãy cầnsắp coi nhưđược
chia thành 2 phần
–Phầnđãsắp: từvịtrí 1 đếni
–Phầnchưasắp: từvịtrí i +1 đếnn
Đỗ Bích Diệp - Khoa CNTT
Sắpxếpkiểulựachọn
–Ví dụ: Sắpxếp dãy sau theo thứtựtăng dần:
zA = {12, 5, 3, 10, 18, 4, 9, 16}
1816161616161616
161818109999
1212121212544
1010101818181818
999910101010
5555512123
44444455
333333312
Lượt7Lượt6Lượt5Lượt4Lượt3Lượt2Lượt1