Advertisement
Guest User

Untitled

a guest
Oct 21st, 2018
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.49 KB | None | 0 0
  1. #include <iostream>
  2. #include "vector"
  3.  
  4. size_t support_sort(std::vector<float> &a, size_t support_index, float support_elem,
  5.                     size_t start_index, size_t finish_index){
  6.     size_t i = start_index;
  7.     bool to_cycle = true;
  8.     float for_exchange = 0;
  9.     if (a[i] > support_elem){
  10.         for_exchange = a[i];
  11.         a[i] = a[support_index];
  12.         a[support_index] = for_exchange;
  13.         support_index = i;
  14.         to_cycle = false;
  15.     }
  16.     i+=1;
  17.     if (to_cycle){
  18.         while((a[i] <= support_elem) && (i < support_index)){
  19.             i += 1;
  20.             if (a[i] > support_elem){
  21.                 for_exchange = a[i];
  22.                 a[i] = a[support_index];
  23.                 a[support_index] = for_exchange;
  24.                 support_index = i;
  25.                 break;
  26.             }
  27.         }
  28.     }
  29.     for (i = support_index; i < finish_index; i++){
  30.         if (a[i] < support_elem){
  31.             if ((i - support_index) > 1){
  32.                 for_exchange = a[i];
  33.                 a[i] = a[support_index+1];
  34.                 a[support_index+1] = for_exchange;
  35.  
  36.                 for_exchange = a[support_index+1];
  37.                 a[support_index+1] = a[support_index];
  38.                 a[support_index] = for_exchange;
  39.             } else{
  40.                 for_exchange = a[i];
  41.                 a[i] = a[support_index];
  42.                 a[support_index] = for_exchange;
  43.             }
  44.             support_index += 1;
  45.         }
  46.     }
  47.     return support_index;
  48. }
  49.  
  50. float k_th_elem(std::vector<float> &a, size_t k, size_t start_index, size_t finish_index){
  51.     size_t support_index = (finish_index+start_index)/2;
  52.     float support_elem = a[support_index];
  53.  
  54.     support_index = support_sort(a, support_index, support_elem, start_index, finish_index);
  55.  
  56.     if (support_index == k){
  57.         return a[k];
  58.     } else{
  59.         if (support_index > k){
  60.             return k_th_elem(a, k, start_index, support_index);
  61.         } else{
  62.             if (support_index < k){
  63.                 return k_th_elem(a, k, support_index, finish_index);
  64.             }
  65.         }
  66.     }
  67. }
  68.  
  69. int main() {
  70.     std::vector<float > a;
  71.     a = {9, 8, 7, 6, 5, 4, 3, 2};
  72.     size_t index = 5;
  73.     std::cout << support_sort(a, index, a[index], 0, a.size()) << "\n";
  74.     for (size_t i = 0; i < a.size(); i++){
  75.         std::cout << a[i] << " ";
  76.     }
  77.    
  78.    
  79.     size_t k = 7;
  80.     std::cout << "\n" << k << "-th element: " << "\n";
  81.     std::cout << k_th_elem(a, k, 0, a.size());
  82.     return 0;
  83. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement