FindKStatistics

#include <iostream>
#include <vector>
using std::vector;
using std::cin;
using std::cout;

// Выполняет разделение массива. Возвращает позицию опорного элемента.
int Partition( vector<int>& arr, int begin, int end )
{
    int pivot = arr[end - 1];
    int i = begin;
    int j = end - 2;
    while( i <= j ) {
        for( ; arr[i] < pivot; ++i ) {}
        for( ; j >= begin && arr[j] >= pivot; --j ) {}
        if( i < j ) {
            std::swap( arr[i++], arr[j--] );
        }
    }
    // i - позиция первого элемента, больше либо равного опорного.
    std::swap( arr[i], arr[end - 1] );
    return i;
}

int FindKStatistics( vector<int>& arr, int k )
{
    int begin = 0;
    int end = static_cast<int>( arr.size() );
    while( true ) {
        int pivotPos = Partition( arr, begin, end );
        if( pivotPos == k ) {
            return arr[k];
        }
        if( pivotPos < k ) {
            begin = pivotPos + 1;
        } else {
            end = pivotPos;
        }
    }
}

int main()
{
    int n = 0;
    cin >> n;
    int k = 0;
    cin >> k;

    vector<int> arr( n, 0 );
    for( int i = 0; i < n; ++i ){
        cin >> arr[i];
    }

    cout << FindKStatistics( arr, k );
    return 0;
}