›
›

Cấu trúc dữ liệu và giải thuật - Sắp xếp

pdf 38 trang vanle 2800
Download
Bạn đang xem 20 trang mẫu của tài liệu "Cấu trúc dữ liệu và giải thuật - Sắp xếp", để 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:

  • pdfcau_truc_du_lieu_va_giai_thuat_sap_xep.pdf

Nội dung text: Cấu trúc dữ liệu và giải thuật - Sắp xếp

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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
  18. 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
  19. 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
  20. 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
  21. 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
  22. 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
  23. 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
  24. 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
  25. 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
  26. Heap sort – Ví dụ khác 26 Cấu trúc dữ liệu và giải thuật - Sắp xếp
  27. 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
  28. 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
  29. 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
  30. 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
  31. 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
  32. 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
  33. 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
  34. 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
  35. Kết quả so sánh 35 Cấu trúc dữ liệu và giải thuật - Sắp xếp
  36. Nhanh nhất? 36 Cấu trúc dữ liệu và giải thuật - Sắp xếp
  37. Độ 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
  38. 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