Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
2.8 kB
2
Indexable
Never
#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
Leave a Comment