Cod sursa(job #2629129)

Utilizator Leonard123Mirt Leonard Leonard123 Data 19 iunie 2020 10:12:02
Problema Sortare prin comparare Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include<bits/stdc++.h>
using namespace std; 

//buckets of bytes
#define maxb 8
#define bucket 0xFF
#define total_bytes (sizeof(vec[1]))
#define get_byte(x) ((x>>(byte*8))&bucket)

int n;

int* read(){
	cin>>n;
	int *v=new int[n];
	for(int i=0; i<n; i++)
		cin>>v[i];	
	return v;
}

void countSort(int byte, int *vec){
	int count[1<<maxb];
	int index[1<<maxb];
	int aux[n+5];
	index[0]=0;
	memset(count,0,sizeof(count));
	for(int i=0; i<n; ++i)
		count[get_byte(vec[i])]++;
	for(int i=1; i<(1<<maxb); ++i)
		index[i]=index[i-1]+count[i-1];
	for(int i=0; i<n; i++)
		aux[index[get_byte(vec[i])]++]=vec[i];
	for(int i=0; i<n; i++)
		vec[i]=aux[i];
}


int main(){
	freopen("algsort.in","r",stdin);
	freopen("algsort.out","w",stdout);
	int *vec=read();
	for(int bit=0; bit<total_bytes; ++bit)
		countSort(bit,vec);
	for(int i=0; i<n; i+=1)
		cout<<vec[i]<<' ';
}