Untitled
unknown
plain_text
a year ago
2.8 kB
8
Indexable
#include <iostream> #include <chrono> #include <random> using namespace std; const int MAX_SIZE = 100000; void selectionSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { int minIndex = i; for (int j = i + 1; j < n; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } swap(arr[i], arr[minIndex]); } } void bubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { swap(arr[j], arr[j + 1]); } } } } void heapSort(int arr[], int n) { // Build heap for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } // One by one extract an element from heap and // place it at the end of sorted array for (int i = n - 1; i >= 0; i--) { // Move current root to end swap(arr[0], arr[i]); // call max heapify on the reduced heap heapify(arr, i, 0); } } void heapify(int arr[], int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; // If left child is larger than root if (left < n && arr[left] > arr[largest]) { largest = left; } // If right child is larger than largest so far if (right < n && arr[right] > arr[largest]) { largest = right; } // If largest is not root if (largest != i) { swap(arr[i], arr[largest]); heapify(arr, n, largest); } } void quickSort(int arr[], int low, int high) { if (low < high) { // pi is the partitioning index int pi = partition(arr, low, high); // Recursively sort elements before // and after partition quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } int partition(int arr[], int low, int high) { // pivot is the element at the center int pivot = arr[high]; // i indicates the current position of smaller element int i = (low - 1); // Iterate through elements // compare each element with pivot for (int j = low; j < high; j++) { if (arr[j] <= pivot) { // If element smaller than pivot is found // swap it with the greater element pointed by i i++; // swap element at i with element at j swap(arr[i], arr[j]); } } // swap pivot with the greater element at i swap(arr[i + 1], arr[high]); // return the partition point return (i + 1); } void generateRandomArray(int arr[], int n) { random_device rd; mt19937 gen(rd()); uniform_int_distribution<> dist(0, MAX_SIZE); for (int i = 0; i < n; i++) { arr[i] = dist(gen); } } void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { cout << arr[i] << " "; } cout << endl; } int main() { int n; cout << "Nhap so phan tu: "; cin
Editor is loading...
Leave a Comment