Cod sursa(job #601106)

Utilizator APOCALYPTODragos APOCALYPTO Data 4 iulie 2011 22:58:06
Problema Sortare prin comparare Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
using namespace std;
#include<iostream>
#include<fstream>
#include<cstdlib>
#define nmax 500010
ofstream fout("algsort.out");
int N,a[nmax];
int select(int l,int r)
{
    int i,p;
    int popiv=rand()%(r-l+1)+l;
    int pivot=a[popiv];
    swap(a[popiv],a[r]);
    int fin=l;
    for(i=l;i<r;i++)
    {
        if(a[i]<pivot)
        {
            swap(a[i],a[fin]);
            fin++;
        }
    }
    swap(a[fin],a[r]);
    return fin;
}

void qsort(int l,int r)
{
//cout<<l<<" "<<r<<"\n";
    if(l>r) return;
    int p=select(l,r);

    qsort(l,p-1);
    qsort(p+1,r);

}

void cit()
{
    ifstream fin("algsort.in");
    fin>>N;
    int i;
    for(i=1;i<=N;i++)
    {

        fin>>a[i];
    }

    fin.close();

}

int main()
{
    srand(time(0));
    cit();
    qsort(1,N);
    int i;
    for(i=1;i<=N;i++)
    {

        fout<<a[i]<<" ";
    }
    fout.close();
    return 0;
}