Cod sursa(job #484247)

Utilizator crawlerPuni Andrei Paul crawler Data 12 septembrie 2010 23:38:42
Problema Sortare prin comparare Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <stdio.h>

#define NMAX 500000
#define nil -1

int theArray[NMAX];

int N;

FILE *inputFile = fopen("algsort.in", "r");

#define BUFFER_SIZE 8192

char buff[BUFFER_SIZE];
int buffIt;

inline int getNumber() {
  int ret = 0;
  
  while (buff[buffIt] < '0' || buff[buffIt] > '9')
    if (++buffIt == BUFFER_SIZE)
      fread(buff, BUFFER_SIZE, 1, inputFile),
      buffIt = 0;

  while (buff[buffIt] >= '0' && buff[buffIt] <= '9') {
    ret = ret * 10 + buff[buffIt] - '0';
    if (++buffIt == BUFFER_SIZE) {
      buffIt = 0;
      fread(buff, BUFFER_SIZE, 1, inputFile);
    }
  }

  return ret;
}

void readArray() {
  N = getNumber();
  for (int i = 0; i < N; ++i) {
    theArray[i] = getNumber();
  }
}

char outputBuffer[8192];

void writeArray() {
  FILE *f = fopen("algsort.out", "w");
  setbuf(f, outputBuffer);

  for (int i = 0; i < N; ++i) {
    fprintf(f, "%d ", theArray[i]);
  }

  fclose(f);
}

void sortArray(int left, int right, int mask) {
  if (left >= right || mask <= 0)
    return ;

  int poz = right;
  for (int i = left; i < poz; ++i)
    if (theArray[i] & mask) {
      int tmp = theArray[--poz];
      theArray[poz] = theArray[i];
      theArray[i] = tmp;
      --i;
      continue;
    }

  sortArray(left, poz, mask >> 1);
  sortArray(poz, right, mask >> 1);
}

void solve() {
  readArray();
  sortArray(0, N, 1<<30);
  writeArray();
}

int main() {
  solve();
  return 0;
}