intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:31

Thêm vào BST
Báo xấu
38
lượt xem 4
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

"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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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

  1. 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.com 1 Ngo Huu Phuc, Le Quy Don Technical University
  2. 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ồng 2 Ngo Huu Phuc, Le Quy Don Technical University
  3. 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
  4. 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
  5. 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 =1 5 Ngo Huu Phuc, Le Quy Don Technical University
  6. 7.1. ShellSort (4/8) #include for(int i=0;i
  7. 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: \n"); int temp; for(i=0;i0; k--) printf("%d\t",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
  8. 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
  9. 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
  10. 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
  11. 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 Don Technical University
  12. 7.2. Mergesort (2/9) Các bước thực hiện:  Bắt đầu từ một mảng có 1 phần tử, nối với mảng thứ hai cũng có 1 phần tử để tạo thành mảng mới có 2 phần tử.  Một cách tương tự, ta nối mảng ba và mảng bốn để được mảng mới có 2 phần tử, tiếp tục như trên cho đến khi hết, như vậy ta đã thực hiện xong một lần sắp xếp (one pass).  Tiếp theo, nối hai mảng có kích thước 2 phần tử lại để được một mảng có kích thước 4 phần tử. Đến khi kết thúc, ta đã qua lần sắp xếp thứ hai.  Tiếp tục quá trình trên cho đến khi chỉ còn 1 mảng, khi đó mảng đã được sắp xếp!!! 12 Ngo Huu Phuc, Le Quy Don Technical University
  13. 7.2. Mergesort (3/9) Hoạt động của thuật toán MergeSort 13 Ngo Huu Phuc, Le Quy Don Technical University
  14. 7.2. Mergesort (4/9) Để thực hiện được thuật toán này cần thiết xây dựng:  Một hàm cho phép nối 2 mảng có kích thước m và n thành mảng có kích thước (m+n).  Cần thêm một hàm cho biết đã nối các mảng liền kề hay chưa? 14 Ngo Huu Phuc, Le Quy Don Technical University
  15. 7.2. Mergesort (5/9) #include mergesort(list,n-1); #include printf("Cac phan tu cua mang sau khi sap #include xep:\n"); #include printlist(list,n); #define MAX 100 getch(); void readlist(int list[],int n); } void printlist(int list[],int n); void readlist(int list[],int n) void merge(int list[],int listtemp[],int k,int m,int n); { void mpass(int list[],int listtemp[],int l,int n); int i; void mergesort(int list[], int n ); printf("Nhap cac phan tu cho mang\n"); void main() { srand( (unsigned)time(NULL)); int list[MAX], n; printf("Nhap so phan tu cho mang\n"); for(i=0;i
  16. 7.2. Mergesort (6/9) void printlist(int list[],int n) while( i
  17. 7.2. Mergesort (7/9) while(i
  18. 7.2. Mergesort (8/9) void mergesort(int list[], int n ) { int l; int listtemp[MAX]; l =1; while (l
  19. 7.2. Mergesort (9/9) Phân tích độ phức tạp của thuật toán MergeSort:  Trong trường hợp tồi nhất: O(N log N)  Trong trường hợp tốt nhất: O(N log N)  Trong trường hợp trung bình: O(N log N) Vì sao?  Nếu n là kích thươc của mảng cần sắp xếp, mỗi lần sắp các nhóm con, độ phức tạp sẽ là O(n), hơn nữa số lần lặp lại quá trình sắp trên là log2n.  Cho tất cả các trường hợp, độ phức tạp của Merge Sort là O(n log2(n)), tuy nhiên cần sử dụng thêm một mảng có kích thước n nữa 19 Ngo Huu Phuc, Le Quy Don Technical University
  20. 7.3. Bucket sort (1/6)  Giả sử các giá trị cần sắp nằm trong khoảng: 0.. m  Thuật toán Bucket Sort thực hiện:  Khởi tạo m chiếc thùng (buckets) được đánh số: 0 … m.  Kiểm tra từng phần tử S[i] trong danh sách S và đưa vào thùng thứ i.  Như vậy, ta có m thùng với các giá trị đã được đưa vào theo đúng trật tự.  Sau đó, sắp lại các phần tử theo từng thùng, dựa trên chỉ số của thùng.  Phương pháp này không cần phép toán so sánh. 20 Ngo Huu Phuc, Le Quy Don Technical University
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2