Bài giảng Cấu trúc dữ liệu và giải thuật - Giải thật sắp xếp - Ngô Hữu Dũng
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và giải thuật - Giải thật sắp xếp - Ngô Hữu Dũng", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
Tài liệu đính kèm:
- bai_giang_cau_truc_du_lieu_va_giai_thuat_giai_that_sap_xep_n.pdf
Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Giải thật sắp xếp - Ngô Hữu Dũng
- TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP THÀNH PHỐ HỒ CHÍ MINH 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
- Sắp xếp – sort Selection Sort Insertion Sort Bubble sort Shell Sort Merge Sort Heap Sort Quick Sort Lưu ý: Các code ở đây chỉ mang tính chất minh hoạ cho giải thuật Có nhiều cách diễn đạt và cải tiến thuật toán 2 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- Các thuật toán sắp xếp 3 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- Interchange sort 51 90 26 23 63 26 90 51 23 63 Thừa vô ích 23 90 51 26 63 23 51 90 26 63 23 26 90 51 63 23 26 51 90 63 Luôn lặp n2 lần 23 26 51 63 90 Có nhiều hoán vị thừa 1. void interchangeSort(int a[], int n) 2. { 3. for(int i=0; i a[j]) 6. swap(&a[i], &a[j]); 7. } 4 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- Insertion sort for i = 2:n, for (k = i; k > 1 and a[k] < a[k-1]; k ) swap a[k,k-1] → invariant: a[1 i] is sorted end 51 90 26 23 63 26 51 90 23 63 Dịch chuyển nhiều phần tử 23 26 51 90 63 Dịch chuyển nhiều lần 23 26 51 63 90 Luôn lặp n2 lần 5 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- Insertion sort – Minh hoạ 1. void insertionSort(int a[], int n) 2. { 3. int i, key, j; 4. for (int i = 1; i = 0 && a[j] > temp) 10. { 11. a[j+1] = a[j]; 12. j = j-1; 13. } 14. a[j+1] = temp; 15. } 16.} 6 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- Selection sort for i = 1:n, k = i for j = i+1:n, if a[j] < a[k], k = j → invariant: a[k] smallest of a[i n] swap a[i,k] → invariant: a[1 i] in final position end 7 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- Selection sort 51 90 26 23 63 23 90 26 51 63 23 26 90 51 63 23 26 51 90 63 23 26 51 63 90 Loại những hoán vị thừa ở thuật toán cơ bản 8 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- Selection sort – Minh hoạ 1. void selectionSort(int a[], int n) 2. { 3. for(int i=0; i<n; i++) 4. { 5. int k = i; 6. for(int j=i+1; j<n; j++) 7. if (a[j]<a[k]) 8. k=j; 9. if(i!=k) 10. swap(&a[i], &a[k]); 11. } 12.} 9 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- Bubble Sort for i = 1:n, swapped = false for j = n:i+1, if a[j] < a[j-1], swap a[j,j-1] swapped = true → invariant: a[1 i] in final position break if not swapped end 10 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- Bubble Sort 51 90 26 23 63 51 90 23 26 63 51 23 90 26 63 23 51 90 26 63 23 51 26 90 63 23 26 51 90 63 23 26 51 63 90 Nhiều lần hoán vị 11 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- Bubble Sort – Minh hoạ 1. void bubbleSort(int a[], int n) 2. { 3. for(int i=0; i i; j ) 7. if(a[j] < a[j-1]) 8. { 9. swap(&a[j], &a[j-1]); 10. swapped = true; 11. } 12. if(!swapped) break; 13. } 14.} 12 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- Shell Sort Tương tự như insertion sort Insertion sort Khi hoán đổi di chuyển từng phần tử liền kề Shell sort Khi hoán đổi di chuyển các phần tử cách nhau khoảng cách gap Sắp xếp mảng con gap Các phần tử cách nhau một khoảng gap gap có thể bắt đầu từ n/2, giảm dần về 1 13 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- Shell Sort – Ví dụ 51 90 26 23 63 26 90 51 23 63 gap = 2 26 23 51 90 63 gap = 2 26 23 51 90 63 gap = 2 23 26 51 90 63 gap = 1 23 26 51 63 90 gap = 1 14 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- Shell Sort – Ví dụ khác Sau một gap = 5: Các phần tử có khoảng cách là 5 được sắp xếp 15 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- Shell Sort – Minh hoạ 1. void shellSort(int a[], int n) 2. { 3. for (int gap = n/2; gap > 0; gap /= 2) 4. { 5. for (int i = gap; i =gap && a[j-gap]>temp; j-=gap) 10. a[j] = a[j - gap]; 11. a[j] = temp; 12. } 13. } 14.} 16 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- Shell Sort – Biến thể khác gap = 1 while gap 0, gap = gap / 3 for k = 1:gap, insertion sort a[k:gap:n] → invariant: each gap-sub-array is sorted end 17 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- Shell Sort – Minh hoạ 1. void shellSort(int a[], int n) 2. { 3. int gap=1; 4. while(gap 0) 6. { 7. gap=gap/3; 8. for(int k=gap; k =gap && a[j-gap]>temp;j-=gap) 13. a[j] = a[j-gap]; 14. a[j] = temp; 15. } 16. } 17.} 18 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- Merge Sort Chia để trị 51 90 26 23 63 Chia thành hai mảng 51 90 26 23 63 con Tiếp tục chia đôi các 51 90 26 23 63 mảng con như cây nhị phân 51 90 26 23 63 Trộn các mảng con và 51 90 26 23 63 sắp xếp tăng dần 26 51 90 23 63 23 26 51 63 90 19 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- Merge sort – Ví dụ khác Trộn Trộn hai mảng đồng thời sắp xếp tăng dần 20 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- Merge Sort – Algorithm # split in half m = n / 2 # recursive sorts sort a[1 m] sort a[m+1 n] # merge sorted sub-arrays using temp array b = copy of a[1 m] i = 1, j = m+1, k = 1 while i <= m and j <= n, a[k++] = (a[j] < b[i]) ? a[j++] : b[i++] → invariant: a[1 k] in final position while i <= m, a[k++] = b[i++] → invariant: a[1 k] in final position 21 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- Merge Sort – Minh hoạ 1. void mergeSort(int a[], int left, int right) 2. { 3. if (left < right) 4. { 5. int mid = (left+right)/2; 6. // Sắp xếp hai nửa trước và sau 7. mergeSort(a, left, mid); 8. mergeSort(a, mid+1, right); 9. // Trộn lại 10. merge(a, left, mid, right); 11. } 12.} 22 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- Merge Sort – Minh hoạ 1. void merge(int a[], int left, int mid, int right) 2. { 3. int i, j, k; 4. int b[mid+1]; 5. for (i = left; i <= mid; i++) 6. b[i] = a[i]; 7. i = left; // Initial index of first subarray 8. j = mid+1; // Initial index of second subarray 9. k = left; // Initial index of merged subarray 10. while (i <= mid && j <= right) 11. a[k++] = (b[i]<a[j])?b[i++]:a[j++]; 12. while (i <= mid) 13. a[k++] = b[i++]; 14.} 23 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- Heap Sort Cấu trúc binary Heap Cây nhị phân đầy đủ Giả sử một nút cha là i Nút con bên trái là 2*i + 1 Nút con bên phải là 2*i + 2 Nút cha (parent node) Lớn hơn hai nút con (max heap) Nhỏ hơn hai nút con (min heap) Heap có thể được biểu diễn Cây nhị phân Mảng 24 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- Heap Sort – Algorithm Giải thuật Heap sort 51 90 26 23 63 B1: Xây dựng max heap 90 51 26 23 63 B2: Phần tử lớn nhất ở gốc B3: Thay thế gốc bằng phần 90 63 26 23 51 tử cuối cùng 51 63 26 23 90 B4: Giảm kích thước heap 63 51 26 23 90 B5: Xây dựng lại max heap 23 51 26 63 90 B6: Lặp lại bước 2 cho đến khi hết mảng 51 23 26 63 90 Vẽ cây nhị phân cho các 26 23 51 63 90 dãy số bên 23 26 51 63 90 25 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- Heap sort – Ví dụ khác 26 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- Heap Sort – Minh hoạ 1. void heapSort(int a[], int n) 2. { 3. // Build heap (rearrange array) 4. for (int i = n / 2 - 1; i >= 0; i ) 5. heapify(a, n, i); 6. 7. // One by one extract an element from heap 8. for (int i=n-1; i>=0; i ) 9. { 10. // Move current root to end 11. swap(&a[0], &a[i]); 12. // call max heapify on the reduced heap 13. heapify(a, i, 0); 14. } 15.} 27 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- Heap Sort – Minh hoạ 1. void heapify(int a[], int n, int i) 2. { 3. int largest = i; // Initialize largest as root 4. int l = 2*i + 1; // left = 2*i + 1 5. int r = 2*i + 2; // right = 2*i + 2 6. // If left child is larger than root 7. if (l arr[largest]) 8. largest = l; 9. // If right child is larger than largest so far 10. if (r arr[largest]) 11. largest = r; 12. // If largest is not root 13. if (largest != i) 14. { 15. swap(&a[i], &a[largest]); 16. // Recursively heapify the affected sub-tree 17. heapify(a, n, largest); 18. } 19. } 28 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- Quick Sort Thuật toán chia để trị (Divide and Conquer) Chọn một phần tử trục (pivot) Ngẫu nhiên, đầu, giữa hoặc cuối Phân vùng danh sách (partition) Tìm vị trí chính xác của phần tử trục Các phần tử nhỏ hơn pivot nằm phía trước Các phần tử lớn hơn pivot nằm phía sau Tiếp tục với các danh sách con 51 90 26 23 63 p <p <p pivot 29 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- Quick Sort – How’s it work? Lấy pivot là điểm phải: 51 90 26 23 63 {51, 90, 26, 23, 63} 51 26 90 23 63 51 26 23 90 63 {51, 26, 23} {63} {90} 51 26 23 63 90 23 26 51 63 90 { } {23} {26, 51} {26} {51} { } 30 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- Quick Sort - Algorithm _# choose pivot_ random swap a[1,rand(1,n)] _# 2-way partition_ k = 1 for i = 2:n, if a[i] < a[1], swap a[++k,i] swap a[1,k] _→ invariant: a[1 k-1] < a[k] <= a[k+1 n]_ _# recursive sorts_ sort a[1 k-1] sort a[k+1,n] 31 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- Quick Sort – Minh hoạ 1. void quickSort(int arr[], int low, int high) 2. { 3. if (low < high) 4. { 5. /* pi is partitioning index, arr[p] is now 6. at right place */ 7. int pi = partition(arr, low, high); 8. 9. // Separately sort elements before 10. // partition and after partition 11. quickSort(arr, low, pi - 1); 12. quickSort(arr, pi + 1, high); 13. } 14. } 32 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- Quick Sort – Minh hoạ 1. int partition (int a[], int low, int high) 2. { 3. int pivot = a[high]; 4. int i = (low - 1); // Index of smaller element 5. 6. for (int j = low; j < high; j++) 7. { 8. // If current element is smaller than or 9. // equal to pivot 10. if (a[j] <= pivot) 11. { 12. i++; // increment index of smaller element 13. swap(&a[i], &a[j]); 14. } 15. } 16. swap(&a[i + 1], &a[high]); 17. return (i + 1); 18. } 33 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- So sánh thực nghiệm Thực hiện 1000 phép lặp cho mỗi hàm Giá trị của mảng được phát sinh ngẫu nhiên b[i] = rand(); Đo thời gian thực hiện của mỗi hàm 1. t = clock(); 2. for(int i=0;i<LOOP; i++) 3. { 4. copy(a, b, n);// b là mảng phát sinh ngẫu nhiên 5. Sort(a, n); 6. } 7. t=clock()-t; // loopTime là thời gian lặp và copy 8. printf("Sorting time: %.2fs\n", (t-loopTime) /(float)CLOCKS_PER_SEC); 34 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- Kết quả so sánh 35 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- Nhanh nhất? 36 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- Độ phức tạp của thuật toán Algorithm Best case Average case Worst case Selection sort O(n2) O(n2) O(n2) Insertion sort O(n) O(n2) O(n2) Bubble sort O(n) O(n2) O(n2) Shell sort O(n) O((nlog(n))2) O((nlog(n))2) Merge sort O(nlogn) O(nlogn) O(nlogn) Heap sort O(nlogn) O(nlogn) O(nlogn) Quick sort O(nlogn) O(nlogn) O(n2) 37 Cấu trúc dữ liệu và giải thuật - Sắp xếp
- Bài tập vận dụng Viết chương trình Phát sinh ngẫu nhiên một mảng Cài đặt các hàm sắp xếp Tính số thao tác của mỗi phương pháp Đánh giá các phương pháp Tìm hiểu hoặc đề xuất phương pháp mới 38 Cấu trúc dữ liệu và giải thuật - Sắp xếp