Cod sursa(job #1013122)

Utilizator ELHoriaHoria Cretescu ELHoria Data 20 octombrie 2013 13:04:18
Problema Sortare prin comparare Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <ctime>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <vector>
 
using namespace std;
 
const int nmax = int(5e5), base = 256;
int n;
int a[nmax];
int bucket[base];
int b[nmax];
 
void lsdRadixSort() {
    for(int k = 0;k < 8;k++) {
		for(int digit = 0;digit < base;digit++) {
			 bucket[digit] = 0;
        }

        for(int i = 0;i < n;i++) {
            bucket[a[i]>>(8*k) & 255]++;
			b[i] = a[i];
        }
    
        for(int digit = 1;digit < base;digit++) {
			bucket[digit] += bucket[digit - 1];
        }

		for(int i = n - 1;i >= 0;i--) {
           a[--bucket[b[i]>>(8*k) & 255]] = b[i];
        }

    }
}
 
void readData() {
    scanf("%d",&n);
     for(int i = 0;i < n;i++) {
         scanf("%d",&a[i]);
     }
}
 
void printData() {
    for(int i = 0;i < n;i++) {
        printf("%d ",a[i]);
    }
    printf("\n");
}
 
 
int main()
{
    freopen("algsort.in","r",stdin);
    freopen("algsort.out","w",stdout);
    readData();
    lsdRadixSort();
    printData();
    return 0;
}