Pagini recente » Cod sursa (job #2148578) | Cod sursa (job #3145126) | Cod sursa (job #53562) | Cod sursa (job #684801) | Cod sursa (job #2529154)
#include <stdio.h>
#include <stdlib.h>
#define NMAX 1000000
int v[NMAX];
void quickSelect( int k, int st, int dr ) {
int i, pozpiv, aux;
while ( st < dr ) {
pozpiv = st; /// Pozitia pivotului este egala cu st
i = st + 1; /// Incepem de la st + 1
while ( i <= dr ) {
if ( v[i] <= v[pozpiv] ) { /// Daca elementul este mai mic sau egal decat pivotul
aux = v[pozpiv + 1]; /// Interschimbam pivotul cu urmatorul element
v[pozpiv + 1] = v[pozpiv];
v[pozpiv] = aux;
pozpiv ++;
if ( v[pozpiv - 1] > v[pozpiv] ) { /// Daca elementul interschimbat anterior nu este chiar elementul mai mic
aux = v[pozpiv - 1]; /// Il interschimbam cu elemntul interschimbat anterior
v[pozpiv - 1] = v[i]; /// cu pivotul
v[i] = aux;
}
}
i ++;
}
if ( k > pozpiv )
if ( pozpiv + 1 == st )
st = pozpiv;
else
st = pozpiv + 1;
else
if ( pozpiv == dr )
dr = pozpiv - 1;
else
dr = pozpiv;
}
}
int main() {
FILE *fin = fopen( "sdo.in", "r" ), *fout = fopen( "sdo.out", "w" );
int n, k, i;
fscanf( fin, "%d%d", &n, &k );
for ( i = 0; i < n; i ++ ) {
fscanf( fin, "%d", &v[i] );
}
quickSelect( k - 1, 0, n - 1 );
fprintf( fout, "%d", v[k - 1] );
fclose( fin );
fclose( fout );
return 0;
}