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 - Ngô Hữu Phước

Giảng viên: TS. Ngo Huu Phuc Tel: 0438 326 077 Mob: 098 5696 580 Email: ngohuuphuc76@gmail.com 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 Ngo Huu Phuc, Le Quy Don Technical University1 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 Ngo Huu Phuc, Le Quy Don Technical University2 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? Ngo Huu Phuc, Le Quy Don Technical University3 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. Ngo Huu Phuc, Le Quy Don Technical University4 7.1. ShellSort (3/8)  Ví dụ: với 13 phần tử, dãy khoảng cách là 1,3,5 Ngo Huu Phuc, Le Quy Don Technical University5 STT 0 1 2 3 4 5 6 7 8 9 10 11 12 Ban đầu 81 94 11 96 12 35 17 95 28 58 41 75 15 KC = 5 35 17 11 28 12 41 75 15 96 58 81 94 95 KC = 3 28 12 11 35 15 41 58 17 94 75 81 96 95 KC = 1 11 12 15 17 28 35 41 58 75 81 94 95 96 7.1. ShellSort (4/8) #include #include #define MAX 100 void inputdata(int* list,int n); void printlist(int* list,int n); void shellsort(int *list, int n, int *incs, int t); void main() { int list[MAX], n; int incs[MAX], t; printf("Nhap so phan tu cua mang:\n"); scanf("%d",&n); inputdata(list,n); printf("Mang da nhap:\n"); printlist(list,n); printf("Nhap so phan tu cua mang khoang cach:"); scanf("%d",&t); printf("Nhap gia tri cua mang khoang cach:"); Ngo Huu Phuc, Le Quy Don Technical University6 for(int i=0;i<t;i++) scanf("%d",&incs[i]); shellsort(list,n,incs,t); printf("Mang da sap xep:\n"); printlist(list,n); getch(); } void inputdata(int* list,int n) { int i; printf("Nhap cac phan tu cua mang\n"); for(i=0;i<n;i++) scanf("%d",&list[i]); fflush(stdin); } 7.1. ShellSort (5/8) void printlist(int* list,int n) { int i; printf("Cac phan tu cua mang: \n"); for(i=0;i<n;i++) printf("%d\t",list[i]); printf("\n"); } Ngo Huu Phuc, Le Quy Don Technical University7 void shellsort(int *list, int n, int *incs, int t) { int i,j,k,h; int temp; for(k=t-1; k>0; k--) for(h=incs[k], i=h; i<n; i+=h) { temp=list[i]; j=i; while(j>=h && list[j-h]>temp) { list[j]=list[j-h]; j-=h; } list[j]=temp; } } 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) Ngo Huu Phuc, Le Quy Don Technical University8 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) Ngo Huu Phuc, Le Quy Don Technical University9 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) Ngo Huu Phuc, Le Quy Don Technical University10 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). Ngo Huu Phuc, Le Quy Don Technical University11 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!!! Ngo Huu Phuc, Le Quy Don Technical University12 7.2. Mergesort (3/9) Ngo Huu Phuc, Le Quy Don Technical University13 Hoạt động của thuật toán MergeSort 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? Ngo Huu Phuc, Le Quy Don Technical University14 7.2. Mergesort (5/9) #include #include #include #include #define MAX 100 void readlist(int list[],int n); void printlist(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); void mergesort(int list[], int n ); void main() { int list[MAX], n; printf("Nhap so phan tu cho mang\n"); scanf("%d",&n); readlist(list,n); printf("Cac phan tu cua mang truoc khi sap xep:\n"); printlist(list,n); Ngo Huu Phuc, Le Quy Don Technical University15 mergesort(list,n-1); printf("Cac phan tu cua mang sau khi sap xep:\n"); printlist(list,n); getch(); } void readlist(int list[],int n) { int i; printf("Nhap cac phan tu cho mang\n"); srand( (unsigned)time(NULL)); for(i=0;i<n;i++) //scanf("%d",&list[i]); list[i]=rand(); } 7.2. Mergesort (6/9) void printlist(int list[],int n) { int i; printf("Cac phan tu trong danh sach: \n"); for(i=0;i<n;i++) printf("%d\t",list[i]); printf("\n"); } // Noi 2 mang da sap xep // Mang thu nhat: tu phan tu thu k den phan tu thu m // Mang thu nhat: tu phan tu thu m+1 den phan tu // thu n void merge(int list[],int listtemp[],int k,int m,int n) { int i,j; i=k; j = m+1; Ngo Huu Phuc, Le Quy Don Technical University16 while( i <= m && j <= n) { if(list[i] <= list[j]) { listtemp[k] = list[i]; i++; k++; } else { listtemp[k] = list[j]; j++; k++; } } 7.2. Mergesort (7/9) while(i <= m) { listtemp[k] = list[i]; i++; k++; } while (j <= n ) { listtemp[k] = list[j]; j++; k++; } } Ngo Huu Phuc, Le Quy Don Technical University17 // Voi do dai l cua moi mang con // noi cac mang con thanh mang lon hon void mpass( int list[],int listtemp[],int l,int n) { int i; i = 0; while( i <= (n-2*l+1)) { merge(list,listtemp,i,(i+l-1),(i+2*l-1)); i = i + 2*l; } if((i+l-1) < n) merge(list,listtemp,i,(i+l-1),n); else while (i <= n ) { listtemp[i] = list[i]; i++; } } 7.2. Mergesort (8/9) void mergesort(int list[], int n ) { int l; int listtemp[MAX]; l =1; while (l <= n ) { mpass(list,listtemp,l,n); l = l*2; mpass(listtemp,list,l,n); l = l*2; } } Ngo Huu Phuc, Le Quy Don Technical University18 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 Ngo Huu Phuc, Le Quy Don Technical University19 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. Ngo Huu Phuc, Le Quy Don Technical University20 7.3. Bucket sort (2/6) 4 2 1 2 0 3 2 1 4 0 2 3 0 Ngo Huu Phuc, Le Quy Don Technical University21 0 0 0 1 1 2 2 2 2 3 3 4 4 0 0 0 1 1 2 2 2 2 3 3 4 4 7.3. Bucket sort (3/6) #include #include #define MAX 100 int inputdata(int* list,int n); void printlist(int* list,int n); void bucketsort(int *list, int n, int m); void main() { int list[MAX], n; // So thung int m; printf("Nhap so phan tu cho mang, toi da = 100\n"); scanf("%d",&n); m = inputdata(list,n); printf("Mang da nhap:\n"); printlist(list,n); bucketsort(list,n,m); printf("Mang da sap xep:\n"); Ngo Huu Phuc, Le Quy Don Technical University22 printlist(list,n); getch(); } int inputdata(int* list,int n) { int i, m; int temp; printf("Nhap cac phan tu duong cho mang\n"); do { scanf("%d",&temp); } while (temp<0); m = temp; list[0] = temp; for(i=1;i<n;i++) { 7.3. Bucket sort (4/6) do { scanf("%d",&temp); } while (temp<0); list[i] = temp; if (m<temp) m = temp; } return m; } void printlist(int* list,int n) { int i; printf("Cac phan tu cua mang: \n"); for(i=0;i<n;i++) printf("%d\t",list[i]); printf("\n"); } Ngo Huu Phuc, Le Quy Don Technical University23 void bucketsort(int *list, int n, int m) { int i,j,k; int bucket[MAX]; // Khoi tao thung for(j=0; j<=m; j++) bucket[j] = 0; for(i=0; i<n; i++) bucket[list[i]]++; i = 0; for(j=0; j<=m; j++) for(k=0; k<bucket[j]; k++) { list[i] = j; i++; } } 7.3. Bucket sort (5/6) Đánh giá độ phức tạp của phương pháp:  Để khởi tạo m thùng, thời gian cần thiết: O(m)  Để đưa các phần tử từ danh sách vào thùng, thời gian cần thiết: O(n)  Để đưa các phần tử từ các thùng vào danh sách cần:O(n)  Lưu ý: mặc dù, trong đoạn này vẫn có 2 vòng lặp lồng nhau, tuy nhiên, số phần tử được xét vẫn chỉ là n phần tử.  Nếu như m nhỏ hơn n (thông thường), độ phức tạp của Bucket Sort là O(n).  Tổng quát hóa, độ phức tạp của phương pháp là: O(n+m) Ngo Huu Phuc, Le Quy Don Technical University24 7.3. Bucket sort (6/6) Một số vấn đề của Bucket Sort:  Có thể áp dụng thuật toán cho các dãy chỉ có các số nguyên dương không? Có thể áp dụng, tuy nhiên số thùng sẽ phụ thuộc vào giá trị lớn nhất của dãy số đó.  Nếu cần sắp 1000 số nguyên dương, giá trị lớn nhất là 999 999, khi đó cần 1 triệu thùng. Như vậy, với n<<m, độ phức tạp của thuật toán là O(m)  Có thể có cách khác giải quyết vấn đề này được không?  Thuật toán sẽ được giới thiệu ở phần sau. Ngo Huu Phuc, Le Quy Don Technical University25 7.4. Radix sort (1/6)  Ý tưởng: lặp lại nhiều lần phương pháp sắp theo Bucket dựa trên biểu diễn của số.  Nếu giá trị lớn nhất là 999999, chỉ cần tối đa 10 bucket (thay cho 1 triệu bucket của phương pháp Bucket Sort)  Phương pháp Radix Sort được sử dụng khi khóa trong quá trình sắp xếp là số nguyên và có giới hạn.  Số lần gọi Bucket Sort (Number of passes) phụ thuộc vào biểu diễn của phần tử lớn nhất. Ngo Huu Phuc, Le Quy Don Technical University26 7.4. Radix sort (2/6) 12 58 37 64 52 36 99 63 18 9 20 88 47 Ngo Huu Phuc, Le Quy Don Technical University27 20 12 52 63 64 36 37 47 58 18 88 9 99 20 12 52 63 64 36 37 47 58 18 88 9 99 Ví dụ: First pass 7.4. Radix sort (3/6) 9 12 18 20 36 37 47 52 58 63 64 88 99 Ngo Huu Phuc, Le Quy Don Technical University28 20 12 52 63 64 36 37 47 58 18 88 9 99 9 12 18 20 36 37 47 52 58 63 64 88 99 Example: Second pass 7.4. Radix sort (4/6)  Nếu cố định p lần dùng Bucket Sort ( p = 6 nếu giá trị lớn nhất không quá 999 999), độ phức tạp của Radix Sort là O(n)  Với mỗi lần dùng Bucket Sort, độ phức tạp là O(n).  Nếu kể thêm thông tin về p, độ phức tạp thực sự là O(pn), với p là số chữ số trong biểu diễn của số lớn nhất.  Chú ý, p = log10m, với m là số lớn nhất trong danh sách. Ngo Huu Phuc, Le Quy Don Technical University29 7.4. Radix sort (5/6)  Radix Sort hoạt động cứng, theo thứ tự trong mỗi lần dùng Bucket Sort.  Hoạt động cứng được hiểu theo nghĩa có thứ tự nhất định (từ phải qua trái đối với biểu diễn số của các phần tử trong danh sách) Ví dụ, 2 số có biểu diễn số đầu tiên giống nhau: 52 và 58 Số 52 xuất hiện trước số 58 trong danh sách, số 52 sẽ có trong danh sách kết quả trước số 58. Ngo Huu Phuc, Le Quy Don Technical University30 7.4. Radix sort (6/6)  Chú ý: chỉ cần 10 bucket cho mỗi lần gọi Bucket Sort.  Radix Sort có thể sử dụng cho chữ cái không? Có thể được bằng cách:  Mỗi từ có số chữ cái có giới hạn.  Sử dụng 27 bucket (có thể thêm nếu có những ký tự lạ) cho mỗi chữ cái và 01 bucket cho ký tự “Space bar”.  Thực hiện tương tự như đối với biểu diễn số, bằng cách tách thành từng ký tự của chữ. Ngo Huu Phuc, Le Quy Don Technical University31/31