tailieunhanh - 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. | 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@ 1 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 . ShellSort 8 . MergeSort 9 . BucketSort 5 . RadixSort 6 Tham khảo 1. Bucket 2. Merge 3. Radix 4. 5. Bài giảng của TS Nguyên Nam Hồng 2 Ngo Huu Phuc Le Quy Don Technical University . 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 . 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 . 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 1 5 Ngo Huu Phuc Le Quy Don Technical University . ShellSort 4 8 include for int i 0 i . 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 quot Cac phan tu cua mang n quot int temp for i 0 i0 k-- printf quot d t quot list i for h incs k i h i h amp amp list j-h gt temp list j list j-h j- h list j temp 7 Ngo Huu Phuc Le Quy Don Technical University . ShellSort 6 8 Tính .