Cod sursa(job #1463470)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 21 iulie 2015 00:14:50
Problema Sortare prin comparare Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <cstdio>
#include <algorithm>
#define NMAX 500007
FILE *fin, *fout;
using namespace std;
int n, v[NMAX];
bool bit(int a, int k)
{
    return (a&(1<<k));
}
void radix(int st, int dr, int lvl)
{
    if(lvl < 0) return ;
    int i = st, j = dr;
    while(i < j)
    {
        while(bit(v[i], lvl) == 0 && i< j) ++i;
        while(bit(v[j], lvl) == 1 && i< j) --j;
        if(i < j) swap(v[i], v[j]);
    }
    if(bit(v[dr], lvl) == 0 || bit(v[st], lvl) == 1)
    {
        radix(st, dr, lvl-1);
        return ;
    }
    radix(st, i-1, lvl-1);
    radix(i, dr, lvl-1);
}
int main()
{
    fin = freopen("algsort.in", "r", stdin);
    fout = freopen("algsort.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 1; i<= n; i++) scanf("%d", &v[i]);
    radix(1, n, 31);
    for(int i = 1; i<= n; i++) printf("%d ", v[i]);printf("\n");
    fclose(fin);
    fclose(fout);
    return 0;
}