Xem mẫu
TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP THÀNH PHỐ HỒ CHÍ MINH
Cấu trúc dữ liệu và giải thuật
Giải thuật sắp xếp
TS. Ngô Hữu Dũng
Sắp xếp – sort
Selection Sort
Insertion Sort
Bubble sort
Shell Sort
Merge Sort
Heap Sort
Quick Sort
Lưu ý: Các code ở đây chỉ mang tính chất minh hoạ
cho giải thuật
2
Có nhiều cách diễn đạt và cải tiến thuật toán
Cấu trúc dữ liệu và giải thuật - Sắp xếp
Các thuật toán sắp xếp
https://www.toptal.com/developers/sorting-algorithms/
3
Cấu trúc dữ liệu và giải thuật - Sắp xếp
Interchange sort
51 90 26 23 63
26 90 51 23 63
23 90 51 26 63
23 51 90 26 63
23 26 90 51 63
23 26 51 90 63
23 26 51 63 90
Thừa vô ích
Luôn lặp n2 lần
Có nhiều hoán vị thừa
1. void interchangeSort(int a[], int n)
2. {
3.
for(int i=0; i 1 and a[k] < a[k-1]; k--)
swap a[k,k-1]
→ invariant: a[1..i] is sorted
end
51 90 26 23 63
26 51 90 23 63
23 26 51 90 63
23 26 51 63 90
5
Dịch chuyển nhiều phần tử
Dịch chuyển nhiều lần
Luôn lặp n2 lần
Cấu trúc dữ liệu và giải thuật - Sắp xếp
nguon tai.lieu . vn
Cấu trúc dữ liệu và giải thuật
Giải thuật sắp xếp
TS. Ngô Hữu Dũng
Sắp xếp – sort
Selection Sort
Insertion Sort
Bubble sort
Shell Sort
Merge Sort
Heap Sort
Quick Sort
Lưu ý: Các code ở đây chỉ mang tính chất minh hoạ
cho giải thuật
2
Có nhiều cách diễn đạt và cải tiến thuật toán
Cấu trúc dữ liệu và giải thuật - Sắp xếp
Các thuật toán sắp xếp
https://www.toptal.com/developers/sorting-algorithms/
3
Cấu trúc dữ liệu và giải thuật - Sắp xếp
Interchange sort
51 90 26 23 63
26 90 51 23 63
23 90 51 26 63
23 51 90 26 63
23 26 90 51 63
23 26 51 90 63
23 26 51 63 90
Thừa vô ích
Luôn lặp n2 lần
Có nhiều hoán vị thừa
1. void interchangeSort(int a[], int n)
2. {
3.
for(int i=0; i 1 and a[k] < a[k-1]; k--)
swap a[k,k-1]
→ invariant: a[1..i] is sorted
end
51 90 26 23 63
26 51 90 23 63
23 26 51 90 63
23 26 51 63 90
5
Dịch chuyển nhiều phần tử
Dịch chuyển nhiều lần
Luôn lặp n2 lần
Cấu trúc dữ liệu và giải thuật - Sắp xếp