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, unsigned long int n)
  42 {
  43         unsigned long int i, j, min;
  44         for(i=0; i<n; i++) {
  45                 min = -1;
  46                 for(j=0; j<n; j++) {
  47                         if (array[j].ord) continue;
  48                         if ((min==-1) || (es_menor(data, array, n, j, min)))
  49                                 min = j;
  50                 }
  51
  52                 array[min].ord = 1;
  53                 array[min].pos_orden = i;
  54         }
  55 }
  56
  57 int generar_salida(char *data, t_BlockSort *array, char *salida, int n)
  58 {
  59         unsigned long int i, j, k;
  60         k=-1;
  61         for(i=0; i<n; i++) {
  62                 for(j=0; j<n; j++) {
  63                         if (array[j].pos_orden == i) {
  64                                 salida[i] = data[array[j].pos_final];
  65                                 if (array[j].pos_inicial == 0) k = i;
  66                         }
  67                 }
  68         }
  69
  70         return k;
  71 }
  72
  73 void block_sorting(char *in, char *out, unsigned long int *k, unsigned long int len)
  74 {
  75         t_BlockSort *array;
  76
  77         array = malloc(sizeof(t_BlockSort)*len);
  78
  79         generar_array(in, array, len);
  80         ordenar_array(in, array, len);
  81         (*k) = generar_salida(in, array, out, len);
  82
  83         free(array);
  84 }
  85
  86 int main(int argc, char *argv[])
  87 {
  88         char *data;
  89         char *salida;
  90         unsigned long int len, i, k;
  91         FILE *fp;
  92
  93         if (argc != 3) {
  94                 printf("Modo de uso : %s <archivo datos> <tamaño pagina>\n", argv[0]);
  95                 return 0;
  96         }
  97
  98         fp = fopen(argv[1], "r");
  99         len = atoi(argv[2]);
 100
 101         data = malloc(sizeof(char)*len);
 102         salida = malloc(sizeof(char)*len);
 103         memset(salida, 0, len*sizeof(char));
 104
 105         for(i=0; i<len; i++)
 106                 data[i] = fgetc(fp);
 107
 108         fclose(fp);
 109
 110         block_sorting(data, salida, &k, len);
 111
 112         printf("Salida = (%s) con k=%ld\n", salida, k);
 113         return 0;
 114 }
 115
 116