Pagini recente » Cod sursa (job #3277196) | Cod sursa (job #1993076) | Cod sursa (job #1792808) | Cod sursa (job #2497181) | Cod sursa (job #392709)
Cod sursa(job #392709)
#include <time.h>
#include <stdlib.h>
#include <stdio.h>
#define N 500001
/*sortarea elementelor cu pointeri, mutarea cheilor la
sfarsit in place; probabil eficient cand elementele
sunt mari si dureaza copierea
*/
int sir[N],p[N];
bool viz[N];
void sort(int st,int dr)
{int aux,s=st,d=dr,pivot=sir[p[st+rand()%(dr-st+1)]];
while(s<d)
{while(sir[p[s]]<pivot){++s;}
while(sir[p[d]]>pivot){--d;}
if(s<=d)
{if(s<d)
{aux=p[s];
p[s]=p[d];
p[d]=aux;
}
++s;
--d;
}
}
if(st<d)sort(st,d);
if(s<dr)sort(s,dr);
}
int main ()
{freopen("algsort.in","r",stdin);
freopen("algsort.out","w",stdout);
int i,j,n,aux;
scanf("%d",&n);
for (i=0;i<n;++i)
{scanf("%d",&sir[i]);
p[i]=i;
}
srand(time(NULL));
sort(0,n-1); //sortare cu pointeri
/*
for (i=0;i<n;i++)
{if(viz[i]==false)
{viz[i]=true;
if(p[i]!=i)
{aux=sir[i];
j=i;
while(p[j]!=i)
{viz[j]=true;
sir[j]=sir[p[j]];
j=p[j];
}
sir[j]=aux;
viz[j]=true;
}
}
}
for (i=0;i<n;i++)
{printf("%d ",sir[i]);
}*/
for (i=0;i<n;i++)
{printf("%d ",sir[p[i]]);
}
return 0;
}