KStatisticsWithTiming

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

// Разделение подмассива по опорному элементу. В качестве опорного берется последний.
// left, right - границы подмассива. left включается, right не включается.
// Возвращает индекс опорного элемента.
int Partition( vector<int>& arr, int left, int right )
{
    assert( right > left );
    int pivot = arr[right - 1];
    int i = left;
    int j = right - 2;

    while( i <= j ) {
        for( ; arr[i] < pivot; ++i );
        for( ; j >= left && !( arr[j] < pivot ); --j ) {}
        if( i < j ) {
            std::swap( arr[i], arr[j] );
        }
    }
    std::swap( arr[i], arr[right - 1] );
    return i;
}

// Поиск k-ой порядковой статистики.
int KStatistics( vector<int>& arr, int k )
{
    assert( k >= 0 );
    assert( k < static_cast<int>( arr.size() ) );

    int left = 0;
    int right = arr.size();
    while( true ) {
        int pivotPos = Partition( arr, left, right );
        if( pivotPos == k ) {
            return arr[k];
        } else if( pivotPos < k ) {
            left = pivotPos + 1;
        } else {
            right = pivotPos;
        }
    }
}

int main()
{
//  freopen( "in.txt", "r", stdin );
//  freopen( "out.txt", "w", stdout );

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

    clock_t start = clock();
    std::cout << KStatistics( arr, k ) << std::endl;
    clock_t end = clock();

    std::cout << end - start;
    return 0;
}