Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 7: Các phương pháp sắp xếp khác

"Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 7: Các phương pháp sắp xếp khác" gồm 4 nội dung tìm hiểu ShellSort, MergeSort, BucketSort, RadixSort.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 7: Các phương pháp sắp xếp khác Cấu trúc dữ liệu và giải thuật Bài 7. Các phương pháp sắp xếp khác Giảng viên: TS. Ngo Huu Phuc Tel: 0438 326 077 Mob: 098 5696 580 Email: ngohuuphuc76@gmail.com1 Ngo Huu Phuc, Le Quy Don Technical University Bài 7. Các phương pháp sắp xếp khác Nội dung: 7.1. ShellSort (8) 7.2. MergeSort (9) 7.3. BucketSort (5) 7.4. RadixSort (6) Tham khảo: 1. Bucket sort.htm 2. Merge Sort.htm 3. Radix sort.htm 4. ShellSort.htm 5. Bài giảng của TS Nguyên Nam Hồng2 Ngo Huu Phuc, Le Quy Don Technical University 7.1. ShellSort (1/8)  Phương pháp này được Donald Shell giới thiệu năm 1959.  Với phương pháp sắp xếp chèn: thực hiện ít phép toán so sánh, nhưng sử dụng nhiều phép di chuyển thừa.  Với phương pháp sắp xếp chọn: thực hiện ít phép toán di chuyển, nhưng sử dụng nhiều phép so sánh.  Có thể có phương pháp hiệu quả hơn không?3 Ngo Huu Phuc, Le Quy Don Technical University 7.1. ShellSort (2/8)  Phương pháp sắp xếp ShellSort còn được gọi là phương pháp sắp xếp giảm độ tăng - diminishing increment sort.  Phương pháp sử dụng một dãy tăng: h1, h2, .. ht  Dãy tăng được bắt đầu từ 1, tối đa đến N-1 (trong thực tế đến N/2). Chưa có đề xuất dãy như thế nào tốt nhất.  Trong dãy này, không nên ch ọn các số là bội của nhau.  Dãy này còn được gọi là dãy khoảng cách, ví dụ 1,3,5.4 Ngo Huu Phuc, Le Quy Don Technical University 7.1. ShellSort (3/8)  Ví dụ: với 13 phần tử, dãy khoảng cách là 1,3,5 STT 0 1 2 3 4 5 6 7 8 9 10 11 12 Ban 81 94 11 96 12 35 17 95 28 58 41 75 15 đầu KC 35 17 11 28 12 41 75 15 96 58 81 94 95 =5 KC 28 12 11 35 15 41 58 17 94 75 81 96 95 =3 KC 11 12 15 17 28 35 41 58 75 81 94 95 96 =15 Ngo Huu Phuc, Le Quy Don Technical University 7.1. ShellSort (4/8)#include for(int i=0;i 7.1. ShellSort (5/8)void printlist(int* list,int n) void shellsort(int *list, int n, int *incs, int t){ { int i; int i,j,k,h; printf(Cac phan tu cua mang: ); int temp; for(i=0;i0; k--) printf(%d ,list[i]); for(h=incs[k], i=h; i=h && list[j-h]>temp) { list[j]=list[j-h]; j-=h; } list[j]=temp; } }7 Ngo Huu Phuc, Le Quy Don Technical University 7.1. ShellSort (6/8)  Tính hiệu quả của thuật toán ShellSort?  Phụ thuộc vào mảng khoảng cách.  Dạng mặc định, do Shell đề xuất:  ht = N/2, hk = hk+1/2 …  Độ phức tạp của thuật toán - O(N2)8 Ngo Huu Phuc, Le Quy Don Technical University 7.1. ShellSort (7/8)  Dãy khoảng cách của Hibbards:  Hk = 2k-1 i.e. 1, 3, 7,  Độ phức tạp: O(N1.5)  Dãy khoảng cách của Sedgewicks:  Có một số dạng được giới thiệu, nổi tiếng trong đó có 2 dạng: 9 * 4i – 9 * 2i + 1, và 4i – 3 * 2i + 1  Độ phức tạp: O(N4/3)9 Ngo Huu Phuc, Le Quy Don Technical University 7.1. ShellSort (8/8)  Độ phức tạp của ShellSort trong trường hợp tồi nhất: O(N2)  Độ phức tạp của ShellSort trong trường hợp tốt nhất: ~ O(N)  Độ phức tạp của ShellSort trong trường hợp trung bình: ~ O(N7/6)10 Ngo Huu Phuc, Le Quy Don Technical University 7.2. Mergesort (1/9)  MergeSort là một thuật toán sắp xếp cho độ phức tạp tương đương với Quick Sort. Ý tưởng:  Ý tưởng cơ bản của MergeSort là nối 2 mảng đã sắp xếp với kích thước m và n thành mảng mới có kích thước (m+n).11 Ngo Huu Phuc, Le Quy D ...