Bài giảng 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

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 />