Cod sursa(job #2288531)

Utilizator catu_bogdan_99Catu Bogdan catu_bogdan_99 Data 23 noiembrie 2018 16:33:08
Problema Statistici de ordine Scor 50
Compilator c-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <stdio.h>
#include <stdlib.h>
#define NMAX 3000005

int V[ NMAX ];

void swap( int *a, int *b ) {

    int c;
    c = *a;
    *a = *b;
    *b = c;

}

int quick_select( int k, int st, int dr ) {

    int i, j, piv;

    if ( st >= dr ) return V[ dr ];

    i = st; j = dr;
    piv = V[ ( i + j ) / 2 ];

    while ( i <= j ) {
        while( V[ i ] < piv ) i++;
        while( piv < V[ j ] ) j--;
        if ( i <= j ) {
            swap( &V[ i ], &V[ j ] );
            i++; j--;
        }
    }
    if ( k >= i ) return quick_select( k, i, dr );
    return quick_select( k, st, j );

}


int main () {

    freopen( "sdo.in", "r", stdin );
    freopen( "sdo.out", "w", stdout );

    int n, i, j, k;

    scanf( "%d%d", &n, &k );
    for ( i = 1; i <= n; ++i )
        scanf( "%d", &V[ i ] );

    printf("%d\n", quick_select( k, 1, n ) );

    return 0;

}