Cod sursa(job #392709)

Utilizator nicolaetitus12Nicolae Titus nicolaetitus12 Data 8 februarie 2010 04:53:54
Problema Sortare prin comparare Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#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;
}