nsz Git - libfirm/blob - ir/be/test/MergeSort.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3
   4 void merge (float *, int, int, int);
   5
   6 /* sort the (sub)array v from start to end */
   7
   8 void merge_sort (float *v, int start, int end) {
   9   int middle;   /* the middle of the subarray */
  10
  11   /* no elements to sort */
  12   if (start == end) return;
  13
  14   /* one element; already sorted! */
  15   if (start == end - 1) return;
  16
  17   /* find the middle of the array, splitting it into two subarrays */
  18   middle = (start + end) / 2;
  19
  20   /* sort the subarray from start..middle */
  21   merge_sort (v, start, middle);
  22
  23   /* sort the subarray from middle..end */
  24   merge_sort (v, middle, end);
  25
  26   /* merge the two sorted halves */
  27   merge (v, start, middle, end);
  28 }
  29
  30 /* merge the subarray v[start..middle] with v[middle..end], placing the
  31  * result back into v.
  32  */
  33 void merge (float *v, int start, int middle, int end) {
  34   int v1_n, v2_n, v1_index, v2_index, i;
  35
  36   float *v1 = malloc((middle - start) * sizeof(*v1));
  37   float *v2 = malloc((end - middle) * sizeof(*v2));
  38
  39   /* number of elements in first subarray */
  40   v1_n = middle - start;
  41
  42   /* number of elements in second subarray */
  43   v2_n = end - middle;
  44
  45   /* fill v1 and v2 with the elements of the first and second
  46    * subarrays, respectively
  47    */
  48   for (i=0; i<v1_n; i++) v1[i] = v[start + i];
  49   for (i=0; i<v2_n; i++) v2[i] = v[middle + i];
  50
  51   /* v1_index and v2_index will index into v1 and v2, respectively... */
  52   v1_index = 0;
  53   v2_index = 0;
  54
  55   /* ... as we pick elements from one or the other to place back
  56    * into v
  57    */
  58   for (i=0; (v1_index < v1_n) && (v2_index < v2_n); i++) {
  59
  60     /* current v1 element less than current v2 element? */
  61     if (v1[v1_index] <= v2[v2_index])
  62
  63       /* if so, this element belong as next in v */
  64       v[start + i] = v1[v1_index++];
  65     else
  66       /* otherwise, the element from v2 belongs there */
  67       v[start + i] = v2[v2_index++];
  68   }
  69   /* clean up; either v1 or v2 may have stuff left in it */
  70
  71   for (; v1_index < v1_n; i++) v[start + i] = v1[v1_index++];
  72   for (; v2_index < v2_n; i++) v[start + i] = v2[v2_index++];
  73
  74   free(v1); free(v2);
  75 }
  76
  77 int main(int argc, char **argv) {
  78   float *f;
  79   int i, len;
  80
  81   printf("MergeSort.c\n");
  82
  83   len = argc - 1;
  84   f = malloc(len * sizeof(*f));
  85
  86   for(i = 0; i < argc - 1; i++) {
  87     if (!sscanf(argv[i + 1], "%f", f + i)) { printf("Argument %d invalid, float expected instead of '%s'!\n", i, argv[i + 1]); return 1; }
  88     printf(" %f\n", f[i]);
  89   }
  90
  91   if (len < 1) {
  92       printf("Usage: MergeSort <list of numbers>\n");
  93       printf("Continuing with default input.\n");
  94       f = (void *)malloc(sizeof(*f) * (len = 6));
  95       f[0] = 3.3; f[1] = 18.18; f[2] = 5.5; f[3] = 99.99; f[4] = 104.104; f[5] = 2.2;
  96   }
  97
  98   // Ausgabe
  99   printf(" array = ");
 100   for(i = 0; i < len - 1; i++) {
 101     printf(" %f,", f[i]);
 102   }
 103   if (len > 0) {
 104     printf(" %f\n", f[len - 1]);
 105   }
 106   // Sortieren
 107   merge_sort(f, 0, len);
 108
 109   // Ausgabe
 110   printf(" sorted array = ");
 111   for(i = 0; i < len - 1; i++) {
 112     printf(" %f,", f[i]);
 113   }
 114   if (len > 0) {
 115     printf(" %f\n", f[len - 1]);
 116   }
 117
 118   return 0;
 119 }