Cod sursa(job #2680966)

Utilizator Remus.RughinisRemus Rughinis Remus.Rughinis Data 4 decembrie 2020 18:32:03
Problema Radix Sort Scor 30
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.8 kb
//#include <stdio.h>
//#include <stdlib.h>
//int v[1000000];
//
//void radix(int b, int e, int bit){
//  int i,j,aux;
//  if(b>=e || bit==-1)
//    return;
//
//  j=b;
//  for(i=b;i<e;i++){
//    if(v[i] & (1<<bit) == 0){
//      aux=v[i];
//      v[i]=v[j];
//      v[j]=aux;
//      j++;
//    }
//  }
//
//  radix(b,j-1,bit-1);
//  radix(j,e,bit-1);
//}
//
//int main(){
//  int n,i,a,b,c,x;
//  FILE *fin, *fout;
//  fin=fopen("radixsort.in","r");
//  fscanf(fin,"%d%d%d%d",&n,&a,&b,&c);
//  fclose(fin);
//
//  ///Generam vectorul
//  x=b;
//  for(i=0;i<=n;i++){ ///Se pare ca nu calculez bine vectorul!
//    if(i%10==0)
//      v[i/10]=x;
//    x=(a * x + b) % c;
//  }
//
//  radix(0,(n/10)-1,30); ///Numerele sunt pana la 111111111111111111111111111111 (30 de 1) in baza 2
//
//  fout=fopen("radixsort.out","w");
//  for(i=0;i<n/10;i++){
//    fprintf(fout,"%d\n",v[i]);
//  }
//  fclose(fout);
//  return 0;
//}


#include <stdio.h>
#include <stdlib.h>
int v[10000000];

void radix(int b, int e, int bit){
  int i,j,aux;
  if(b>=e || bit==-1)
    return;

  j=b;
  for(i=b;i<=e;i++){
    if((v[i] & (1<<bit)) == 0){
      aux=v[i];
      v[i]=v[j];
      v[j]=aux;
      j++;
    }
  }

  radix(b,j-1,bit-1);
  radix(j,e,bit-1);
}

int main(){
  int n,i,a,b,c,x;
  FILE *fin, *fout;
  fin=fopen("radixsort.in","r");
  fscanf(fin,"%d%d%d%d",&n,&a,&b,&c);
  fclose(fin);

  ///Generam vectorul
  x=b;
  for(i=0;i<n;i++){ ///Se pare ca nu calculez bine vectorul!
    v[i]=x;
    x=(a * x + b) % c;
  }

  radix(0,n-1,30); ///Numerele sunt pana la 111111111111111111111111111111 (30 de 1) in baza 2

  fout=fopen("radixsort.out","w");
  for(i=0;i<n;i++){
    if(i%10==0)
      fprintf(fout,"%d ",v[i]);
  }
  fclose(fout);
  return 0;
}