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