NikolaevMisha/3.1/new

#include <iostream>
/*
Даны неотрицательные целые числа n,k и массив целых чисел из [0..10^9] размера n. Требуется найти k-ю порядковую статистику. т.е. напечатать число, которое бы стояло на позиции с индексом k (0..n-1) в отсортированном массиве. Напишите нерекурсивный алгоритм.
Требования к дополнительной памяти: O(n). Требуемое среднее время работы: O(n).
Функцию Partition следует реализовывать методом прохода двумя итераторами в одном направлении. Описание для случая прохода от начала массива к концу:
Выбирается опорный элемент. Опорный элемент меняется с последним элементом массива.
Во время работы Partition в начале массива содержатся элементы, не бОльшие опорного. Затем располагаются элементы, строго бОльшие опорного. В конце массива лежат нерассмотренные элементы. Последним элементом лежит опорный.
Итератор (индекс) i указывает на начало группы элементов, строго бОльших опорного.
Итератор j больше i, итератор j указывает на первый нерассмотренный элемент.
Шаг алгоритма. Рассматривается элемент, на который указывает j. Если он больше опорного, то сдвигаем j.
Если он не больше опорного, то меняем a[i] и a[j] местами, сдвигаем i и сдвигаем j.
В конце работы алгоритма меняем опорный и элемент, на который указывает итератор i.

3_1. Реализуйте стратегию выбора опорного элемента “медиана трёх”. Функцию Partition реализуйте методом прохода двумя итераторами от начала массива к концу.

*/


int medium(int* arr, int i, int j, int k) // находит медиану трех
{
    if( (arr[i] <= arr[j]) && (arr[j] <= arr[k]))
    {
        return j;
    }
    if( (arr[k] <= arr[j]) && (arr[j] <= arr[i]))
    {
        return j;
    }
    if( (arr[j] <= arr[k]) && (arr[k] <= arr[i]))
    {
        return k;
    }
    if( (arr[i] <= arr[k]) && (arr[k] <= arr[j]))
    {
        return k;
    }
    if( (arr[j] <= arr[i]) && (arr[i] <= arr[k]))
    {
        return i;
    }
    if( (arr[k] <= arr[i]) && (arr[i] <= arr[j]))
    {
        return i;
    }

}

int main()
{

    int n;
    std::cin >> n;
    int k;
    std::cin >> k;
    int A[n];
    for(int i = 0; i < n; ++ i)
    {
        std::cin >> A[i];
    }

    int i = 0;
    int j = 0;
    int start = 0;
    int finish = n-1;
    do
    {
        std::swap(A[finish] , A[medium(A , start , finish, (start + finish)/2)]); // реализация Partition
        while(j < finish)
        {
            if(A[j] > A[finish])
            {
                ++j;
            }
            else
            {
                std:: swap(A[j] , A[i]);
                ++i;
                ++j;
            }
        }
        std::swap(A[finish] , A[i]);
        if(i == k)
        {
            break;
        }
        if(i < k)
        {
            ++i;
            j = i;
            start = i;
        }
        if(i > k)
        {
            finish = i - 1;
            i =  start;
            j = start;
        }
    }
    while(true);
    std::cout << A[i];
    return 0;
}