KShah

Untitled

Oct 23rd, 2021
836
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <climits>
  3. #include <cstring>
  4. #include <cassert>
  5. #include <algorithm>
  6.  
  7. int partition(int arr[], int l, int r, int x) {
  8.     int i;
  9.     for (i = l; i <= r - 1; ++i) {
  10.         if (x == arr[i]) {
  11.             break;
  12.         }
  13.     }
  14.     std::swap(arr[r], arr[i]);
  15.    
  16.     i = l;
  17.     for (int j = l; j <= r - 1; ++j) {
  18.         if (x <= arr[j]) {
  19.             continue;
  20.         } else {
  21.             std::swap(arr[j], arr[i]);
  22.             ++i;
  23.         }
  24.     }
  25.     std::swap(arr[r], arr[i]);
  26.     return i;
  27. }
  28.  
  29. int findMedian(int arr[], int n) {
  30.     std::sort(arr, arr+n);
  31.     return arr[n/2];
  32. }
  33.  
  34. int QuickSelect(int arr[], int left, int right, int k) {
  35.     int size = right - left + 1;
  36.  
  37.     int i, 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 = QuickSelect(median, 0, i - 1, i / 2);
  50.     } else {
  51.         mediansOfMedians = median[0];
  52.     }
  53.      
  54.     int pos = partition(arr, left, right, mediansOfMedians);
  55.        
  56.     if (pos - left > k - 1) {
  57.         return QuickSelect(arr, left, pos - 1, k);
  58.     } else if (pos - left < k - 1) {
  59.         return QuickSelect(arr, pos + 1, right, k - pos + left - 1);
  60.     }
  61.     return arr[pos];
  62. }
  63.  
  64. int main() {
  65.     std::ios_base::sync_with_stdio(false);
  66.     std::cin.tie(nullptr);
  67.     std::cout.tie(nullptr);
  68.     int n, k;
  69.     std::cin >> n >> k;
  70.     int* array = new int[n];
  71.     for (int i = 0; i < n; ++i) {
  72.         std::cin >> array[i];
  73.     }
  74.    
  75.     std::cout << QuickSelect(array, 0, n - 1, k + 1);
  76.  
  77.     delete[] array;
  78.     return 0;
  79. }
  80.  
RAW Paste Data