Cod sursa(job #392705)

Utilizator nicolaetitus12Nicolae Titus nicolaetitus12 Data 8 februarie 2010 04:24:13
Problema Sortare prin comparare Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <stdio.h>
#include <algorithm>
#define N 500001
/*sortarea elementelor cu mutarea elementelor la sfarsit
  eficient cand elementele sunt mari si dureaza copierea
*/
using namespace std;
int sir[N],p[N];
bool viz[N];
int comp(int x,int y)
{if(sir[x]<sir[y])
  return true;
 return false;
}

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;
 }

 sort(p,p+n,comp);

 for (i=0;i<n;i++)
 {if(viz[i]==false)
  {viz[i]=true;
   j=i;
   aux=sir[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]);
 }
 return 0;
}