Cod sursa(job #2273617)

Utilizator marian013Giugioiu Marian Constantin marian013 Data 31 octombrie 2018 20:02:58
Problema Statistici de ordine Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include<fstream>
#include  <cstdlib>
#include <ctime>
using namespace std;
int v[3000002];
int part(int st, int dr){
    int i = st - 1, j = dr + 1, p = v[(st+dr)/2];
    while(1)
    {
        do
		{
			++i;
		} while(v[i] < p);
		do
		{
			--j;
		} while(p < v[j]);
		if(i < j)
			swap(v[i], v[j]);
		else
			return j;
    }
}
void quicksort(int st, int dr, int k)
{
	if(dr == st)
		return;
	int q = part(st, dr);
	int t = q-st+1;
	if(t >= k)
		quicksort(st, q, k);
	else
		quicksort(q+1, dr, k-t);
}
int main()
{
    srand(time(NULL));
    int n, i, k;
    ifstream f("sdo.in");
    ofstream g("sdo.out");
    f>>n>>k;
    for(i = 1; i <=n ; i++)
        f>>v[i];
    quicksort(1, n, k);
    g<<v[k];
}