Cod sursa(job #2612073)

Utilizator paulvlad34Munteanu Vlad Paul paulvlad34 Data 8 mai 2020 14:27:54
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include<iostream>
#include<fstream>
using namespace std;

int getMax(int v[],int n){
	int mx=v[0];
	for (int i=1;i<n;i++)
		if (v[i]>mx)
			mx=v[i];
	return mx;
	
}

void count(int v[],int n,int k){
	int output[n];
	int i,countV[10]={0};
	
	for (i=0;i<n;i++)
		countV[(v[i]/k)%10]++;
	for (i=1;i<10;i++)
		countV[i]+=countV[i-1];
	
	for (i=n-1;i>=0;i--){
		output[countV[(v[i]/k)%10]-1]=v[i];
		countV[(v[i]/k)%10]--;
	}
	
	for (i=0;i<n;i++)
		v[i]=output[i];
	
}

void radix(int v[],int n){
	int m=getMax(v,n);
	for (int k=1;m/k>0;k*=10)
		count(v,n,k);
	
}

int main(){
	ifstream f("radixsort.in");
	ofstream f1("radixsort.out");
	int n,a,b,c;
	f>>n>>a>>b>>c;
	int v[n];
	for (int i=0;i<n;i++)
		if (i==0)
			v[i]=b;
		else
			v[i]=(a*v[i-1]+b)%c;
	radix(v,n);
	
	for (int i=0;i<n;i+=10){
		f1<<v[i]<<" ";
	}
			
	
	
}