Cod sursa(job #601126)

Utilizator APOCALYPTODragos APOCALYPTO Data 4 iulie 2011 23:44:22
Problema Sortare prin comparare Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 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,j;

    int popiv;
    popiv=rand()%(r-l+1)+l;
    swap(a[l],a[popiv]);

    int pivot;
    pivot=a[l];
    i=l-1;
    j=r+1;
    while(1)
    {
        do
        {
            i++;
        }while(a[i]<pivot);
        do
        {
            j--;
        }while(a[j]>pivot);
        if(i<j)
        {
            swap(a[i],a[j]);
        }
        else return j;
        /*for(;a[i]<pivot ;) i++;
        for(;a[j]>pivot ;) j--;
        swap(a[i],a[j]);*/
    }
    /*for(i=1;i<=N;i++)
    {

        cout<<a[i]<<" ";
    }
    cout<<"\n";*/
    //return j;
}

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

    qsort(l,p);
    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;
}