KStatOptimized

#include <assert.h>
#include <iostream>
#include <vector>
using std::vector;

// Разбиение массива по опорному элементу.
// Возвращает индекс, на котором будет расположен опорный элемент после разбиения.
// Опорный элементы выбирается неэффективно - в конце массива.
int Partition( vector<int>& data, int left, int right )
{
    assert( left < right );
    const int& pivot = data[right - 1];
    int i = left;
    int j = right - 2;
    while( i <= j ) {
        // Двигаем i вправо до элемента больше либо равного pivot.
        for( ; data[i] < pivot; ++i ) {}
        // Двигаем j влево до элемента меньше либо равного pivot.
        // Так добиваемся того, что в случае большого количества элементов равных pivot,
        // они расположатся примерно равномерно слева и справа.
        for( ; j >= left && pivot < data[j]; --j ) {}
        if( i < j ) {
            std::swap( data[i], data[j] );
            ++i;
            --j;
        }
    }
    std::swap( data[i], data[right - 1] );
    return i;
}

// Возвращает k-ую порядковую статистику. k считается от 0.
int KStat( vector<int>& data, int k )
{
    assert( k >= 0 && k < static_cast<int>( data.size() ) );
    int left = 0;
    int right = data.size(); // Не включаем right.
    while( true ) {
        int pivotPos = Partition( data, left, right );
        if( pivotPos == k ) {
            return data[k];
        }
        if( pivotPos > k ) {
            right = pivotPos;
        } else {
            left = pivotPos + 1;
        }
    }
}

int main()
{
    int n = 0;
    int k = 0;
    std::cin >> n >> k;
    vector<int> data( n );
    for( int i = 0; i < n; ++i ) {
        std::cin >> data[i];
    }
    std::cout << KStat( data, k );
    return 0;
}