Cod sursa(job #2341682)

Utilizator IoanStoicaStoica Ioan IoanStoica Data 12 februarie 2019 09:26:45
Problema Sortare prin comparare Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <iostream>
#include <fstream>
#define k 500002
#define ll unsigned long long
using namespace std;

ifstream f("algsort.in");
ofstream g("algsort.out");

ll v[k],aux[k];
void sortare(ll in[],ll fin[],int a,int b,int bit)
{
    if(a==b)fin[a]=in[a];
    if(a>=b || bit<0)return ;
    int st=a-1,dr=b+1,i;
    for(i=a;i<=b;i++)
        if((1<<bit)&in[i])
            fin[--dr]=in[i];
        else fin[++st]=in[i];
    sortare(fin,in,a,st,bit-1);
    sortare(fin,in,dr,b,bit-1);
}


int main()
{
    int n;
    int bit;
    ll m=0;
    f>>n;
    for(int i=1;i<=n;i++)
    {
        f>>v[i];
        m=max(m,v[i]);
    }
    for(bit=0;;bit++)
        if(1<<(bit+1)> m)
            break;
    sortare(v,aux,1,n,30);
    for(int i=1;i<=n;i++)
        g<<v[i]<<" ";

}