KShah

Untitled

Oct 23rd, 2021
820
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstring>
  3. #include <cassert>
  4. #include <algorithm>
  5.  
  6. int partition(int arr[], int l, int r, long long x) {
  7.     int i;
  8.     for (i = l; i <= r - 1; ++i) {
  9.         if (x == arr[i]) {
  10.             break;
  11.         }
  12.     }
  13.     std::swap(arr[r], arr[i]);
  14.  
  15.     i = l;
  16.     for (int j = l; j <= r - 1; ++j) {
  17.         if (x <= arr[j]) {
  18.             continue;
  19.         } else {
  20.             std::swap(arr[j], arr[i]);
  21.             ++i;
  22.         }
  23.     }
  24.     std::swap(arr[r], arr[i]);
  25.     return i;
  26. }
  27.  
  28. int findMedian(int arr[], int n) {
  29.     std::sort(arr, arr+n);
  30.     return arr[n/2];
  31. }
  32.  
  33. int QuickSelect(int arr[], int left, int right) {
  34.     int size = right - left + 1;
  35.  
  36.     int i;
  37.     int median[(size + 4) / 5];
  38.     for (i = 0; i < size / 5; i++) {
  39.         median[i] = findMedian(arr + left + i * 5, 5);
  40.     }
  41.     // if there is sub_array in the end with len less that 5
  42.     if (i * 5 < size) {
  43.         median[i] = findMedian(arr + left + i * 5, size % 5);
  44.         ++i;
  45.     }
  46.  
  47.     int mediansOfMedians;
  48.     if (i == 1) {
  49.         mediansOfMedians = median[0];
  50.     } else {
  51.         mediansOfMedians = QuickSelect(median, 0, i - 1);
  52.    }
  53.  
  54.     return mediansOfMedians;
  55. }
  56.  
  57. void QuickSort(int arr[], int left, int right) {
  58.     if (left >= right) return;
  59.     if (left < right) {
  60.         int pivot = QuickSelect(arr, left, right);
  61.         int ind = partition(arr, left, right, pivot);
  62.  
  63.         QuickSort(arr, left, ind - 1);
  64.         QuickSort(arr, ind + 1, right);
  65.         //return ind;
  66.     }
  67. }
  68.  
  69. int main() {
  70.     std::ios_base::sync_with_stdio(false);
  71.     std::cin.tie(nullptr);
  72.     std::cout.tie(nullptr);
  73.     int n;
  74.     std::cin >> n;
  75.     int* array = new int[n];
  76.     for (int i = 0; i < n; ++i) {
  77.         std::cin >> array[i];
  78.     }
  79.  
  80.     //std::cout << QuickSelect(array, 0, n - 1) << "\n";
  81.     QuickSort(array, 0, n - 1);
  82.     for (int i = 0; i < n; ++i) {
  83.         std::cout << array[i] << " ";
  84.     }
  85.  
  86.     delete[] array;
  87.     return 0;
  88. }
  89.  
RAW Paste Data