Pagini recente » Rezultatele filtrării | Cod sursa (job #719529) | Rezultatele filtrării | Rezultatele filtrării | Cod sursa (job #1538561)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXN 500000
void readData(int *n, int *v)
{
int i;
scanf("%d",n);
for(i = 1; i <= *n; i++)
scanf("%d",&v[i]);
}
void printVector(int n, int *v)
{
int i;
for(i = 1; i <= n; i++)
printf("%d ",v[i]);
}
void swap(int *x, int *y)
{
int aux = *x;
*x = *y;
*y = aux;
}
int partition(int lo, int hi, int *v)
{
int i = lo + 1, j = hi, p;
p = lo + rand()%(hi-lo+1);
swap(&v[p],&v[lo]);
while(1)
{
for( ; v[ i ] <= v[lo] && i <= hi; i++);
for( ; v[ j ] >= v[lo] && j >= lo + 1; j--);
if(i > hi) break;
if(j <= lo) break;
if(i >= j) break;
swap(&v[i],&v[j]);
}
swap(&v[j],&v[lo]);
return j;
}
void sort(int lo, int hi, int *v)
{
if(lo > hi)
return;
int pos = partition(lo,hi,v);
sort(lo,pos-1,v);
sort(pos+1,hi,v);
}
int main()
{
freopen("algsort.in","r",stdin);
freopen("algsort.out","w",stdout);
int n, v[MAXN+1];
readData(&n,v);
srand(time(NULL));
sort(1,n,v);
printVector(n,v);
return 0;
}