Cod sursa(job #450043)

Utilizator S7012MYPetru Trimbitas S7012MY Data 7 mai 2010 16:56:08
Problema Statistici de ordine Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <ctime>
using namespace std;


int n,v[500001];

int partitie(int p, int r) {
	int x,i,j;
	x=v[p];
	i=p-1;
	j=r+1;
	while (1) {
		do {
			j--;
		} while (v[j]>x);
		do {
			i++;
		}
		while(v[i]<x);
		if(i<j) swap(v[i],v[j]);
		else return j;
	}
}

int partitie_aleatoare (int p, int r) {
	int i;
	i=(rand() % (r-p)) + p + 1;
	//i=(r+p)/2;
	swap(v[p],v[i]);
	return partitie(p,r);
}

void qsort_aleator(int p, int r) {
	int q;
	if(p<r) {
		q=partitie_aleatoare(p,r);
		qsort_aleator(p,q);
		qsort_aleator(q+1,r);
	}
}

int main()
{
	srand( time(NULL) );
	int i,k;
	freopen("sdo.in","r",stdin);
	freopen("sdo.out","w",stdout);
	scanf("%d %d",&n,&k);
	for(i=1; i<=n; i++) scanf("%d",&v[i]);
	qsort_aleator(1,n);
	printf("%d ", v[k]);
	return 0;
}