Cod sursa(job #1721991)

Utilizator elena.marinicaMarinica Elena-Georgiana elena.marinica Data 26 iunie 2016 23:08:57
Problema Statistici de ordine Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>
#include <fstream>

#define NMAX 3000004

using namespace std;

int v[NMAX];
int N;

int quick_sort(int v[], int lower, int upper, int k) {
	
	srand(time(NULL));
	
	if (lower < upper) {
		
		int pos = rand() % ((upper - lower) + lower);
		int piv = v[pos];
		
		std::swap(v[pos], v[upper]);
		
		int p = lower;
		
		for (int i = lower; i < upper; i++) {
			
			if(v[i] <= piv) {
				std::swap(v[i], v[p]);
				p++;
			}
		}
		
		std::swap(v[upper], v[p]);
		
		if (k < p) {
			return quick_sort(v, lower, p - 1, k);
		}
		else if (k > p) {
			return quick_sort(v, p + 1, upper, k);
		}
		else {
			return v[k];
		}
	}
	
}

int main() {
	
	ifstream fin("sdo.in");
	ofstream fout("sdo.out");
	
	int k, x;
	
	fin >> N >> k;
	
	for (int i = 1; i <= N; i++) {
		fin >> x;
		v[i] = x;
	}
	
	x = quick_sort(v, 1, N, k);
	
	fout << x;
}