ex1
unknown
plain_text
2 years ago
3.8 kB
8
Indexable
#include <iostream> // Hàm in mảng void printArray(int arr[], int size) { for (int i = 0; i < size; ++i) { std::cout << arr[i] << " "; } std::cout << std::endl; } // Thuật toán sắp xếp chọn (Selection Sort) void selectionSort(int arr[], int size) { for (int i = 0; i < size - 1; ++i) { int minIndex = i; for (int j = i + 1; j < size; ++j) { if (arr[j] < arr[minIndex]) { minIndex = j; } } std::swap(arr[i], arr[minIndex]); } } // Thuật toán sắp xếp chèn (Insertion Sort) void insertionSort(int arr[], int size) { for (int i = 1; i < size; ++i) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; --j; } arr[j + 1] = key; } } // Thuật toán sắp xếp nổi bọt (Bubble Sort) void bubbleSort(int arr[], int size) { for (int i = 0; i < size - 1; ++i) { for (int j = 0; j < size - i - 1; ++j) { if (arr[j] > arr[j + 1]) { std::swap(arr[j], arr[j + 1]); } } } } // Thuật toán sắp xếp nhanh (Quick Sort) int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = low - 1; for (int j = low; j < high; ++j) { if (arr[j] <= pivot) { ++i; std::swap(arr[i], arr[j]); } } std::swap(arr[i + 1], arr[high]); return i + 1; } void quickSort(int arr[], int low, int high) { if (low < high) { int pivotIndex = partition(arr, low, high); quickSort(arr, low, pivotIndex - 1); quickSort(arr, pivotIndex + 1, high); } } // Thuật toán sắp xếp trộn (Merge Sort) void merge(int arr[], int left, int middle, int right) { int n1 = middle - left + 1; int n2 = right - middle; int L[n1], R[n2]; for (int i = 0; i < n1; ++i) L[i] = arr[left + i]; for (int j = 0; j < n2; ++j) R[j] = arr[middle + 1 + j]; int i = 0, j = 0, k = left; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; ++i; } else { arr[k] = R[j]; ++j; } ++k; } while (i < n1) { arr[k] = L[i]; ++i; ++k; } while (j < n2) { arr[k] = R[j]; ++j; ++k; } } void mergeSort(int arr[], int left, int right) { if (left < right) { int middle = left + (right - left) / 2; mergeSort(arr, left, middle); mergeSort(arr, middle + 1, right); merge(arr, left, middle, right); } } // Thuật toán sắp xếp heap (Heap Sort) void heapify(int arr[], int size, int root) { int largest = root; int left = 2 * root + 1; int right = 2 * root + 2; if (left < size && arr[left] > arr[largest]) largest = left; if (right < size && arr[right] > arr[largest]) largest = right; if (largest != root) { std::swap(arr[root], arr[largest]); heapify(arr, size, largest); } } void heapSort(int arr[], int size) { for (int i = size / 2 - 1; i >= 0; --i) heapify(arr, size, i); for (int i = size - 1; i >= 0; --i) { std::swap(arr[0], arr[i]); heapify(arr, i, 0); } } int main() { int arr[] = {64, 25, 12, 22, 11}; int size = sizeof(arr) / sizeof(arr[0]); // Chọn một trong các hàm sắp xếp dưới đây để sử dụng // selectionSort(arr, size); // insertionSort(arr, size); // bubbleSort(arr, size); // quickSort(arr, 0, size - 1); // mergeSort(arr, 0, size - 1); // heapSort(arr, size); // In mảng sau khi sắp xếp printArray(arr, size); return 0; }
Editor is loading...
Leave a Comment