KShah

Untitled

Oct 24th, 2021
740
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2.  
  3. int findMedian(int* arr, int size){
  4.     for (int i = 0; i < size - 1; ++i){
  5.         for (int j = i + 1; j < size; ++j){
  6.             if (arr[i] > arr[j]){
  7.                 std::swap(arr[i], arr[j]);
  8.             }
  9.         }
  10.     }
  11.     return arr[(size - 1) / 2];
  12. }
  13.  
  14. int QuickSelect(int* arr, int size, int k);
  15.  
  16. int GetPivot(int* arr, int size){
  17.     if (size < 5){
  18.         return findMedian(arr, size);
  19.     }
  20.     int* medians = new int[(size + 4) / 5];
  21.     int medsize = 0;
  22.     for (int i = 0; i < size - size % 5; i += 5){
  23.         medians[medsize++] = findMedian(arr + i, 5);
  24.     }
  25.     if (size % 5){
  26.         medians[medsize++] = findMedian(arr + size - 1 - size % 5, size % 5);
  27.     }
  28.     int medianOfMedians = QuickSelect(medians, medsize, (medsize - 1) / 2);
  29.     delete[] medians;
  30.     return medianOfMedians;
  31. }
  32.  
  33. void Partition(int* arr, int size, int pivot){
  34.     int start = 0, mid = size - 1, fin = size - 1;
  35.     while (start != mid){
  36.         if (arr[start] >= pivot){
  37.             std::swap(arr[start], arr[mid]);
  38.             mid--;
  39.         }
  40.         else{
  41.             start++;
  42.         }
  43.     }
  44.     while (mid != fin){
  45.         if (arr[mid] > pivot){
  46.             std::swap(arr[mid], arr[fin]);
  47.             fin--;
  48.         }
  49.         else{
  50.             mid++;
  51.         }
  52.     }
  53. }
  54.  
  55. int QuickSelect(int* arr, int size, int k){
  56.     if (size == 1){
  57.         return arr[0];
  58.     }
  59.     int pivot = GetPivot(arr, size);
  60.     Partition(arr, size, pivot);
  61.     int count_less = 0, count_not_more = 0;
  62.     while (arr[count_less] < pivot){
  63.         count_less++;
  64.         count_not_more++;
  65.     }
  66.     while (arr[count_not_more] <= pivot){
  67.         count_not_more++;
  68.     }
  69.     if (k >= count_not_more){
  70.          return QuickSelect(arr + count_not_more, size - count_not_more, k - count_not_more);
  71.     }
  72.     if (k < count_less){
  73.         return QuickSelect(arr, count_less, k);
  74.     }
  75.     return pivot;
  76.    
  77. }
  78.  
  79. void QuickSort(int* arr, int size){
  80.     if (size == 1){
  81.         return;
  82.     }
  83.  
  84.     int pivot = QuickSelect(arr, size, (size - 1) / 2);
  85.     Partition(arr, size, pivot);
  86.     int count_less = 0, count_not_more = 0;
  87.     while (arr[count_less] < pivot){
  88.         count_less++;
  89.     }
  90.     while (arr[count_not_more] <= pivot){
  91.         count_not_more++;
  92.     }
  93.     if (count_less != 0){
  94.         QuickSort(arr, count_less);
  95.     }
  96.     if (size - count_not_more != 0) {
  97.         QuickSort(arr + count_not_more, size - count_not_more);
  98.     }
  99. }
  100.  
  101. int main(){
  102.     std::ios_base::sync_with_stdio(false);
  103.     std::cin.tie(nullptr); std::cout.tie(nullptr);
  104.    
  105.     int n;
  106.     std::cin >> n;
  107.    
  108.     int* arr = new int[n];
  109.     for (int i = 0; i < n; i++){
  110.         std::cin >> arr[i];
  111.     }
  112.    
  113.     QuickSort(arr, n);
  114.     for (int i = 0; i < n; i++){
  115.         std::cout << arr[i] << " ";
  116.     }
  117.     std::cout << "\n";
  118.     delete[] arr;
  119.     return 0;
  120. }
  121.  
RAW Paste Data