Cod sursa(job #865110)

Utilizator zalmanDanci Emanuel Sebastian zalman Data 26 ianuarie 2013 01:26:46
Problema Sortare prin comparare Scor 20
Compilator c Status done
Runda Arhiva educationala Marime 0.88 kb
#include <stdio.h>

#define NMAX 500001

int N, tab[NMAX], i;

void read(void)
{
    FILE *f = fopen("algsort.in", "r");

    fscanf(f, "%d", &N);
    for(i = 0; i < N; ++i)
        fscanf(f, "%d", &tab[i]);

    fclose(f);
}

void radix_sort(int l, int r, int b)
{
    int i, j, t;

    if(l >= r || b == -1)
        return;

    i = l, j = r;
    do{
        while(!((tab[i] >> b) & 1) && (i <= j))
            i++;
        while(((tab[j] >> b) & 1) && (j >= i))
            j--;

        if(i <= j)
            t = tab[i], tab[i] = tab[j], tab[j] = t;
    }while(i <= j);

    radix_sort(l, i-1, b-1);
    radix_sort(j+1, r, b-1);
}

void print(void)
{
    FILE *g = fopen("algsort.out", "w");

    for(i = 0; i < N; ++i)
        fprintf(g, "%d ", tab[i]);

    fclose(g);
}

int main(void)
{
    read();
    radix_sort(0, N-1, 15);
    print();
}