TTUD60TH-2: Tìm kiếm và sắp xếp

1 bình luận cho TTUD60TH-2: Tìm kiếm và sắp xếp

• 

  22/09/2021 - 16:21

  admin  says:

  #include <iostream> #include <algorithm> using namespace std; const int N = 10; int a[N] = { 10, 14, 19, 26, 27, 27, 27, 35, 42, 44 }; // sap xep noi bot: n phan tu dau tien cua mang a void bubble_sort(int a[], int n) { bool swapped = true; while (swapped) { swapped = false; for (int i = 1; i < n; i++) if (a[i] < a[i-1]) { swap(a[i], a[i-1]); swapped = true; } } } // sap xep chen: n phan tu dau tien cua mang a void insertion_sort(int a[], int n) { for (int k = 1; k < n; k++) { int last = a[k], j = k; while (j > 0 && a[j-1] > last) { a[j] = a[j-1]; j--; } a[j] = last; } } // sap xep chon: n phan tu dau tien cua mang a void selection_sort(int a[], int n) { for (int k = 0; k < n-1; k++) { int m = k; for (int i = k+1; i < n; i++) if (a[m] > a[i]) m = i; swap(a[k], a[m]); } } // mang phu dung cho sap xep tron int TA[N]; // tron hai day con a[L..M] va a[M+1..R] void merge(int a[], int L, int M, int R) { int i = L, j = M+1; for (int k = L; k <= R; k++) if (i > M) TA[k] = a[j++]; else if (j > R) TA[k] = a[i++]; else if (a[i] < a[j]) TA[k] = a[i++]; else TA[k] = a[j++]; for (int k = L; k <= R; k++) a[k] = TA[k]; } // sap xep tron: n phan tu tu vi tri L den vi tri R void merge_sort(int a[], int L, int R) { if (L < R) { int M = (L + R) / 2; merge_sort(a, L, M); merge_sort(a, M+1, R); merge(a, L, M, R); } } // phan hoach mang lam hai int partition(int a[], int L, int R) { int mid = (L + R) / 2; int pivot = a[mid]; swap(a[mid], a[R]); int store = L; for (int i = L; i <= R-1; i++) if (a[i] < pivot) { swap(a[store], a[i]); store++; } swap(a[store], a[R]); return store; } // sap xep nhanh: n phan tu tu vi tri L den vi tri R void quick_sort(int a[], int L, int R) { if (L < R) { int M = partition(a, L, R); quick_sort(a, L, M-1); quick_sort(a, M+1, R); } } // chinh lai heap do loi cua phan tu i, heap toi da n phan tu void heapify(int a[], int i, int n) { int L = i * 2, R = i * 2 + 1; int m = i; if (L <= n && a[L] > a[m]) m = L; if (R <= n && a[R] > a[m]) m = R; if (m != i) { swap(a[i], a[m]); heapify(a, m, n); } } // tao dong tu a[1..n] void build_heap(int a[], int n) { for (int i = n / 2; i >= 1; i--) heapify(a, i, n); } // sap xep vun: n phan tu cua a tinh tu a[1] void heap_sort(int a[], int n) { build_heap(a, n); for (int i = n; i > 1; i--) { swap(a[1], a[i]); heapify(a, 1, i-1); } } int main() { } </algorithm></iostream>

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125

  #include <iostream> #include <algorithm> using namespace std;   const int N = 10; int a[N] = { 10, 14, 19, 26, 27, 27, 27, 35, 42, 44 };   // sap xep noi bot: n phan tu dau tien cua mang a void bubble_sort(int a[], int n) { bool swapped = true; while (swapped) { swapped = false; for (int i = 1; i < n; i++) if (a[i] < a[i-1]) { swap(a[i], a[i-1]); swapped = true; } } }   // sap xep chen: n phan tu dau tien cua mang a void insertion_sort(int a[], int n) { for (int k = 1; k < n; k++) { int last = a[k], j = k; while (j > 0 && a[j-1] > last) { a[j] = a[j-1]; j--; } a[j] = last; } }   // sap xep chon: n phan tu dau tien cua mang a void selection_sort(int a[], int n) { for (int k = 0; k < n-1; k++) { int m = k; for (int i = k+1; i < n; i++) if (a[m] > a[i]) m = i; swap(a[k], a[m]); } }   // mang phu dung cho sap xep tron int TA[N];   // tron hai day con a[L..M] va a[M+1..R] void merge(int a[], int L, int M, int R) { int i = L, j = M+1; for (int k = L; k <= R; k++) if (i > M) TA[k] = a[j++]; else if (j > R) TA[k] = a[i++]; else if (a[i] < a[j]) TA[k] = a[i++]; else TA[k] = a[j++]; for (int k = L; k <= R; k++) a[k] = TA[k]; }   // sap xep tron: n phan tu tu vi tri L den vi tri R void merge_sort(int a[], int L, int R) { if (L < R) { int M = (L + R) / 2; merge_sort(a, L, M); merge_sort(a, M+1, R); merge(a, L, M, R); } }   // phan hoach mang lam hai int partition(int a[], int L, int R) { int mid = (L + R) / 2; int pivot = a[mid]; swap(a[mid], a[R]); int store = L; for (int i = L; i <= R-1; i++) if (a[i] < pivot) { swap(a[store], a[i]); store++; } swap(a[store], a[R]); return store; }   // sap xep nhanh: n phan tu tu vi tri L den vi tri R void quick_sort(int a[], int L, int R) { if (L < R) { int M = partition(a, L, R); quick_sort(a, L, M-1); quick_sort(a, M+1, R); } }   // chinh lai heap do loi cua phan tu i, heap toi da n phan tu void heapify(int a[], int i, int n) { int L = i * 2, R = i * 2 + 1; int m = i; if (L <= n && a[L] > a[m]) m = L; if (R <= n && a[R] > a[m]) m = R; if (m != i) { swap(a[i], a[m]); heapify(a, m, n); } }   // tao dong tu a[1..n] void build_heap(int a[], int n) { for (int i = n / 2; i >= 1; i--) heapify(a, i, n); }   // sap xep vun: n phan tu cua a tinh tu a[1] void heap_sort(int a[], int n) { build_heap(a, n); for (int i = n; i > 1; i--) { swap(a[1], a[i]); heapify(a, 1, i-1); } }   int main() {   }   </algorithm></iostream>

  Trả lời