Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include "vector"
- size_t support_sort(std::vector<float> &a, size_t support_index, float support_elem,
- size_t start_index, size_t finish_index){
- size_t i = start_index;
- bool to_cycle = true;
- float for_exchange = 0;
- if (a[i] > support_elem){
- for_exchange = a[i];
- a[i] = a[support_index];
- a[support_index] = for_exchange;
- support_index = i;
- to_cycle = false;
- }
- i+=1;
- if (to_cycle){
- while((a[i] <= support_elem) && (i < support_index)){
- i += 1;
- if (a[i] > support_elem){
- for_exchange = a[i];
- a[i] = a[support_index];
- a[support_index] = for_exchange;
- support_index = i;
- break;
- }
- }
- }
- for (i = support_index; i < finish_index; i++){
- if (a[i] < support_elem){
- if ((i - support_index) > 1){
- for_exchange = a[i];
- a[i] = a[support_index+1];
- a[support_index+1] = for_exchange;
- for_exchange = a[support_index+1];
- a[support_index+1] = a[support_index];
- a[support_index] = for_exchange;
- } else{
- for_exchange = a[i];
- a[i] = a[support_index];
- a[support_index] = for_exchange;
- }
- support_index += 1;
- }
- }
- return support_index;
- }
- float k_th_elem(std::vector<float> &a, size_t k, size_t start_index, size_t finish_index){
- size_t support_index = (finish_index+start_index)/2;
- float support_elem = a[support_index];
- support_index = support_sort(a, support_index, support_elem, start_index, finish_index);
- if (support_index == k){
- return a[k];
- } else{
- if (support_index > k){
- return k_th_elem(a, k, start_index, support_index);
- } else{
- if (support_index < k){
- return k_th_elem(a, k, support_index, finish_index);
- }
- }
- }
- }
- int main() {
- std::vector<float > a;
- a = {9, 8, 7, 6, 5, 4, 3, 2};
- size_t index = 5;
- std::cout << support_sort(a, index, a[index], 0, a.size()) << "\n";
- for (size_t i = 0; i < a.size(); i++){
- std::cout << a[i] << " ";
- }
- size_t k = 7;
- std::cout << "\n" << k << "-th element: " << "\n";
- std::cout << k_th_elem(a, k, 0, a.size());
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement