Cod sursa(job #1299762)

Utilizator alexandru.ghergutAlexandru-Gabriel Ghergut alexandru.ghergut Data 23 decembrie 2014 20:56:20
Problema Statistici de ordine Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <cstdlib>
using namespace std;

void quickSort(int left, int right, int k, long long a[]);

int main()
{
    srand(time(NULL));
    long long n, k, i;
    ifstream f("sdo.in");
    f >> n >> k;

    long long *M = new long long[n];
    M[0] = 0;
    for (i = 0; i < n; i++)
        f >> M[i];
    f.close();

    quickSort(0, n - 1, k, M);
    ofstream g("sdo.out");
    g << M[k - 1];
    g.close();

    delete [] M;

    return 0;
}

void quickSort(int left, int right, int k, long long a[])
{
    int i = left, j = right;
    long long pivot = a[left + (rand() % (right - left) + 1)];
    long long aux;

    while (i <= j)
    {
        while (a[i] < pivot)
            i++;
        while (a[j] > pivot)
            j--;
        if (i <= j)
        {
            aux = a[i];
            a[i] = a[j];
            a[j] = aux;
            i++;
            j--;
        }
    }

    if (left < j && k >= left + 1 && k <= j + 1)
        quickSort(left, j, k, a);
    else if (i < right && k >= i + 1 && k <= right + 1)
        quickSort(i, right, k, a);
}