Cod sursa(job #1075323)

Utilizator RampageSergiu Caraian Rampage Data 8 ianuarie 2014 21:02:14
Problema Statistici de ordine Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <cstdlib>
#include <ctime>
#include <fstream>
using namespace std;

ifstream f("sdo.in");
ofstream g("sdo.out");

int partitie (int v[], int ls, int rd)
{
    srand(time(0));
    int p = rand()%(rd-ls+1)+ls;
    swap(v[p],v[rd]);
    int i=ls, j=rd;

    while(i<j)
    {
        while(v[i]<=v[rd] && i<j)
            i++;
        while(v[j]>v[rd] && i<j)
            j--;
        if(i<j)
            swap(v[i],v[j]);
    }

    swap(v[i],v[rd]);
    return i;
}

int sdo(int v[],int ls, int rd, int k)
{
    if(k==ls)
        return v[ls];
    else if (ls<rd)
    {
        int p = partitie(v,ls,rd);
        if(k==p)
            return v[p];
        else if (k<p)
            return sdo(v,ls,p-1,k);
        else if (k>p)
            return sdo(v,p+1,rd,k);
    }
}

void qs(int v[], int ls, int rd)
{
    if(ls<rd)
    {
        int p = partitie(v,ls,rd);
        qs(v,ls,p-1);
        qs(v,p+1,rd);
    }
}

int main()
{
    int n,k,v[301];
    f>>n>>k;

    for(int i=1; i<=n; ++i)
        f>>v[i];

   if(k==1)
        g<<v[1];
    else g<<sdo(v,1,n,k);
    return 0;
}