Cod sursa(job #563311)

Utilizator ILDottoreBogdan Stoian ILDottore Data 24 martie 2011 21:58:48
Problema Sortare prin comparare Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<cstdio>
#include<algorithm>
using namespace std;
FILE *f=fopen("algsort.in","r");
FILE *g=fopen("algsort.out","w");

long n,v[500000];


long pivot(long p,long q)
{long st=p,dr=q;
long  poz = st + rand() % (dr - st + 1);
long aux = v[poz]; v[poz] = v[st]; v[st] = aux;
long x = v[st];

while(st<dr)
{  while(st<dr&&v[dr]>=x) dr--;
v[st]=v[dr];
   while (st<dr&&v[st]<=x) st++;
v[dr]=v[st];}

v[st]=x;
return st;}


void quicksort(long p,long q)
{ long m;

m=pivot(p,q);
if (m-1>p) quicksort(p,m-1);
if (m+1<q) quicksort(m+1,q);

}


int main()
{ fscanf(f,"%ld",&n);
long i;
for (i=1;i<=n;i++)
fscanf(f,"%ld",&v[i]);

quicksort(1,n);

for (i=1;i<=n;i++)
fprintf(g,"%ld ",v[i]);

fclose(f);
fclose(g);
return 0;
}