vio.c

   1 /* vio.c: Sort an array using an 'indirect sorting array'.
   2  *
   3  * I don't know whether the right translation is really
   4  * 'indirect sorting array', but the portuguese name for
   5  * this is 'vetor indireto de ordenacao'.
   6  *
   7  * The basic idea is: instead of moving array's elements
   8  * from a position to another, we use another array only
   9  * to store the indexes and move only the indexes.
  10  *
  11  * This can save time if you're sorting an array of big
  12  * structures, because you'll only move integers instead
  13  * of the structs itself.
  14  *
  15  * Luiz Fernando N. Capitulino
  16  * <lcapitulino@gmail.com>
  17  */
  18 #include <stdio.h>
  19 #include <stdlib.h>
  20 #include <time.h>
  21
  22 /* sort_vio(): sort an array of length 'len' pointed by 'p'
  23  * using an 'indirect sorting array' (vio, in portuguese).
  24  * Uses insertion sort. */
  25 void sort_vio(int *p, int *vio, int len)
  26 {
  27         int idx, i, j;
  28
  29         for (i = 0; i < len; i++)
  30                 vio[i] = i;
  31
  32         for (i = 1; i < len; i++) {
  33                 idx = i;
  34
  35                 for (j = i - 1; j >= 0 && p[vio[j]] > p[idx]; j--)
  36                         vio[j + 1] = vio[j];
  37
  38                 vio[j + 1] = idx;
  39         }
  40 }
  41
  42 /* show_array_vio(): print an array of length 'len'
  43  * pointed by 'p' using an 'indirect sorting array'
  44  * (vio, in portuguese). */
  45 void show_array_vio(int *p, int *vio, int len)
  46 {
  47         int i;
  48
  49         for (i = 0; i < len; i++)
  50                 printf("%d ", p[vio[i]]);
  51         printf("\n");
  52 }
  53
  54 /* show_array(): print an array of length 'len'
  55  * pointed by 'p'. */
  56 void show_array(int *p, int len)
  57 {
  58         int i;
  59
  60         for (i = 0; i < len; i++)
  61                 printf("%d ", p[i]);
  62         printf("\n");
  63 }
  64
  65 #define SIZE 10
  66
  67 int main(void)
  68 {
  69         int array[SIZE], vio[SIZE], i;
  70
  71         srand(time(NULL));
  72
  73         for (i = 0; i < SIZE; i++)
  74                 array[i] = rand() % SIZE;
  75
  76         show_array(array, SIZE);
  77         sort_vio(array, vio, SIZE);
  78         show_array_vio(array, vio, SIZE);
  79
  80         return 0;
  81 }