otros/blocksorting/bs.c

   1
   2 /* Block Sorting Optimizado en memoria! */
   3
   4 #include <string.h>
   5 #include <stdlib.h>
   6 #include <stdio.h>
   7
   8 typedef struct _bs_t_ {
   9         unsigned long int pos_inicial;
  10         unsigned long int pos_final;
  11         unsigned long int pos_orden;
  12         char ord; /* indice si esta ordenada */
  13 } t_BlockSort;
  14
  15 char es_menor(char *data, t_BlockSort *array, int n, int i, int j)
  16 {
  17         unsigned long int pi, pj, k;
  18
  19         for(k=0; k<n; k++) {
  20                 pi = (array[i].pos_inicial+k)%n;
  21                 pj = (array[j].pos_inicial+k)%n;
  22
  23                 if (data[pi] > data[pj]) return 0;
  24                 if (data[pi] < data[pj]) return 1;
  25         }
  26
  27         return 0;
  28 }
  29
  30 void generar_array(char *data, t_BlockSort *array, unsigned long int n)
  31 {
  32         int i;
  33         for(i=0; i<n; i++) {
  34                 array[i].pos_inicial = i;
  35                 array[i].pos_final = (i+n-1)%n;
  36                 array[i].pos_orden = 0;
  37                 array[i].ord = 0;
  38         }
  39 }
  40
  41 void ordenar_array(char *data, t_BlockSort *array, t_BlockSort *ord, unsigned long int n)
  42 {
  43         unsigned long int i, j, min;
  44
  45         for(i=0; i<n; i++) {
  46                 min = -1;
  47                 for(j=0; j<n; j++) {
  48                         if (array[j].ord) continue;
  49                         if ((min==-1) || (es_menor(data, array, n, j, min)))
  50                                 min = j;
  51                 }
  52
  53                 array[min].ord = 1;
  54                 array[min].pos_orden = i;
  55
  56                 ord[i] = array[min];
  57         }
  58 }
  59
  60 int generar_salida(char *data, t_BlockSort *array, char *salida, int n)
  61 {
  62         unsigned long int i, k;
  63         k=-1;
  64         for(i=0; i<n; i++) {
  65                 salida[i] = data[array[i].pos_final];
  66                 if (array[i].pos_inicial == 0) k = i;
  67         }
  68         return k;
  69 }
  70
  71 void block_sorting(char *in, char *out, unsigned long int *k, unsigned long int len)
  72 {
  73         static t_BlockSort *array = NULL;
  74         static t_BlockSort *ord = NULL;
  75
  76         if (!array) array = malloc(sizeof(t_BlockSort)*len);
  77         if (!ord) ord = malloc(sizeof(t_BlockSort)*len);
  78
  79         generar_array(in, array, len);
  80         ordenar_array(in, array, ord, len);
  81         (*k) = generar_salida(in, ord, out, len);
  82 }
  83
  84 int main(int argc, char *argv[])
  85 {
  86         char *data;
  87         char *salida;
  88         unsigned long int len, i, k;
  89         FILE *fp;
  90         char c;
  91
  92         if (argc != 3) {
  93                 printf("Modo de uso : %s <archivo datos> <tamaño pagina>\n", argv[0]);
  94                 return 0;
  95         }
  96
  97         fp = fopen(argv[1], "r");
  98         len = atoi(argv[2]);
  99
 100         data = malloc(sizeof(char)*len);
 101         salida = malloc(sizeof(char)*len);
 102
 103         while ((c = fgetc(fp)) != EOF) {
 104                 memset(salida, 0, len*sizeof(char));
 105                 i = 0;
 106                 while ((c!=EOF) && (i < len)) {
 107                         data[i++] = c;
 108                         c = fgetc(fp);
 109                 }
 110                 block_sorting(data, salida, &k, (i<len)?i:len);
 111                 printf("Salida = (%s) con k=%ld\n", salida, k);
 112         }
 113         fclose(fp);
 114
 115         return 0;
 116 }
 117
 118