Cod sursa(job #1704017)

Utilizator stoianmihailStoian Mihail stoianmihail Data 17 mai 2016 21:59:54
Problema Sortare prin comparare Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.91 kb
/** trieSort **/
#include <stdio.h>
#include <string.h>
#include <ctype.h>

#define Dragoste 4096
#define MAX_BIT 30
#define NIL -1

struct trie {
  int count;
  trie *son[2];

  trie() {
    this -> count = 0;
    memset(this -> son, NULL, sizeof(this -> son));
  }
};

trie *root = new trie;

int pos = Dragoste;
char buff[Dragoste];

char getChar(FILE *f) {
  if (pos == Dragoste) {
    fread(buff, 1, Dragoste, f);
    pos = 0;
  }
  return buff[pos++];
}

void fscanf(FILE *f, const char *arg, int *result) {
  *result = 0;
  char c;

  do {
    c = getChar(f);
  } while (!isdigit(c));
  do {
    (*result) = (*result << 3) + (*result << 1) + c - '0';
    c = getChar(f);
  } while (isdigit(c));
}

void insert(trie *nod, int x, int bit) {
  if (bit == NIL) {
    nod -> count++;
    return;
  }

  int next = (x >> bit) & 1;
  if (nod -> son[next] == NULL) {
    nod -> son[next] = new trie;
  }
  insert(nod -> son[next], x, bit - 1);
}

int erase(trie *nod, int x, int bit) {
  if (bit == NIL) {
    nod -> count--;
  } else {
    int next = (x >> bit) & 1;
    if (erase(nod -> son[next], x, bit - 1)) {
      nod -> son[next] = NULL;
    }
  }
  return nod != root && nod -> count == 0 && nod -> son[0] == NULL && nod -> son[1] == NULL;
}

int search(trie *nod, int bit, int result = 0) {
  if (bit == NIL) {
    return result;
  }
  if (nod -> son[0] != NULL) {
    return search(nod -> son[0], bit - 1, result);
  } else {
    return search(nod -> son[1], bit - 1, result | (1 << bit));
  }
}

int main(void) {
  int N, i, val;
  FILE *f = fopen("algsort.in", "r");

  fscanf(f, "%d", &N);
  for (i = 1; i <= N; i++) {
    fscanf(f, "%d", &val);
    insert(root, val, MAX_BIT);
  }
  fclose(f);

  freopen("alsort.out", "w", stdout);
  for (i = 1; i <= N; i++) {
    val = search(root, MAX_BIT);
    erase(root, val, MAX_BIT);
    fprintf(stdout, "%d ", val);
  }
  fclose(stdout);

  /// Multumim Doamne!
  puts("Doamne ajuta!");
  return 0;
}