Cod sursa(job #460322)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 1 iunie 2010 21:54:41
Problema Statistici de ordine Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <stack>

using namespace std;

vector<int> V;

int partition (int Left, int Right){
	int piv, aux, i = Left - 1, j = Right + 1;
	piv = V[(Left + Right) >> 1];

	while (1){
		do {++i;} while (V [i] < piv);
		do {--j;} while (V [j] > piv);

		if (i < j){
			aux  = V[i];
			V[i] = V[j];
			V[j] = aux;
		}

		else
			return j;
	}
}

void quick_sort(int Left, int Right, int K){
	if (Left < Right){
		int Middle = partition (Left, Right);
		if (K <= Middle)
			quick_sort (Left, Middle, K);
		else
			quick_sort (Middle + 1, Right, K);
	}
}

int main(){
    int N, K, i, a;

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

    scanf("%d%d", &N, &K);

    srand(time(NULL));

    for (i = 1; i <= N; ++i){
        scanf("%d", &a);
        V.push_back(a);
    }

    quick_sort(0, N - 1, K - 1);

	printf("%d\n", V[K - 1]);
}