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

   1 /*
   2  * Project:     GCC-firm
   3  * File name:   test/HeapSort.java
   4  * Purpose:     sorting with heapsort
   5  * Author:
   6  * Modified by: Michael Beck (for GCC-firm)
   7  * Created:     XX.11.2001
   8  * CVS-ID:      $Id$
   9  * Copyright:   (c) 2003 Universitaet Karlsruhe
  10  * Licence:
  11  * URL:         http://www-info1.informatik.uni-wuerzburg.de/staff/wolf/teaching/pi1_ws98/java/Heapsort.java
  12  * Bugs:        Fails for input 5,3,4,7,99
  13  */
  14
  15 #include <stdlib.h>
  16 #include <stdio.h>
  17
  18 /**
  19  * Heapsort-Algorithmus laut Vorlesung.
  20  */
  21 /** Array mit Heap */
  22 int *a;
  23 /** Größe des Heaps */
  24 int N;
  25
  26 /**
  27  * Tauscht die Elemente a[i] und a[j].
  28  */
  29 void exchange(int i,int j) {
  30   int v;
  31   v = a[i];
  32   a[i] = a[j];
  33   a[j] = v;
  34 }
  35
  36 /**
  37  * Läßt a[k] im Feld aufsteigen.
  38  */
  39 void upheap(int k) {
  40   while ((k > 0) && (a[k] < a[k / 2])) {
  41     exchange(k, k / 2);
  42     k = k / 2;
  43   }
  44 }
  45
  46 /**
  47  * Fügt das neue Element v in den Heap der Größe N
  48  * ein und erhöht N um 1
  49  */
  50 void insert(int v) {
  51   a[N] = v;
  52   upheap(N);
  53   N++;
  54 }
  55
  56 /**
  57 * Läßt a[k] im Feld versickern.
  58 */
  59 void downheap(int k) {
  60   int j = 2 * k;
  61   if (j < N) {    // a[k] hat linken Sohn a[j]
  62     if (j + 1 < N)   // a[k] hat auch rechten Sohn a[j+1]
  63       if (a[j] > a[j + 1])
  64         j++;        // Jetzt ist a[j] der kleinere Sohn von a[k]
  65     if (a[k] > a[j]) {
  66       exchange(k, j);
  67       downheap(j);
  68     }
  69   }
  70 }
  71
  72 /**
  73  * Liefert als Resultat das Heap-Element a[k], entfernt a[k]
  74  * aus dem Heap und stellt die Heap-Eigenschaft wieder her.
  75  */
  76 int removeh(int k) {
  77   int v = a[k];
  78   a[k] = a[--N];
  79   if ((k > 0) && (a[k] < a[k / 2]))
  80     upheap(k);
  81   else
  82     downheap(k);
  83   return v;
  84 }
  85
  86 /**
  87  * Aufbau des Heaps durch downheap.
  88  */
  89 void heapaufbau1(void) {
  90   int k;
  91
  92   for (k = N / 2; k >= 1; k--)
  93     downheap(k);
  94 }
  95
  96 /**
  97  * Aufbau des Heaps durch insert.
  98  */
  99 void heapaufbau2(int *b, int len) {
 100   int k;
 101   N = 0;
 102   for (k = 0; k < len; ++k)
 103     insert(b[k]);
 104 }
 105
 106 /**
 107  * Sortiert das gegebene Feld b mit den oben angegebenen
 108  * Heap-Methoden und gibt das sortierte Feld zurück.
 109  */
 110 int *heapsort(int *b, int len) {
 111   int i, k;
 112   int *c;
 113
 114   // Globale Variablen für die Heap-Methoden setzen
 115   a = (void *)malloc(sizeof(*a) * len);
 116   heapaufbau2(b, len);
 117
 118   // Ergebnis in c kopieren
 119   c = (void *)malloc(sizeof(*c) * len);
 120   for (k = 0; k < len; k++)
 121     c[k] = removeh(0);
 122   return c;
 123 }
 124
 125 /**
 126  * Ein einfaches Beispielprogramm. Alle Argumente des Programms müssen
 127  * Zahlen sein.
 128  * Bsp:<pre>
 129  * java Heapsort 6 13 17 42 9 3 5
 130  * array={6,13,17,42,9,3,5}
 131  * sorted array={3,5,6,9,13,17,42}
 132  * </pre>
 133  */
 134 int main (int argc, char *argv[]) {
 135   // Umwandeln der Argumente in Zahlen
 136   int *b;
 137   int i, len;
 138
 139   printf("Heap.c\n");
 140
 141   len = argc - 1;
 142
 143   if (len < 1) {
 144       static int _b[] = {3, 18, 5, 99, 104, 2};
 145       printf("Usage: HeapSort <list of numbers>\n");
 146       printf("Continuing with default input.\n");
 147       b = _b;
 148       len = sizeof(_b)/sizeof(_b[0]);
 149   }
 150   else {
 151     b = (void *)malloc(len * sizeof(*b));
 152
 153     for(i = 0; i < argc-1; i++) {
 154       b[i] = atoi(argv[i+1]);
 155       printf(" %d\n", b[i]);
 156     }
 157   }
 158
 159   // Ausgabe
 160   //System.out.print("array={");
 161   // printf("length of array to sort: %d -- first element b[0]: %d\n", len, b[0]);
 162   printf(" array = ");
 163   for(i = 0; i < len - 1; i++) {
 164     printf(" %d,", b[i]);
 165   }
 166   if (len > 0) {
 167     printf(" %d\n", b[len - 1]);
 168   }
 169   // Sortieren
 170   b = heapsort(b, len);
 171
 172   // Ausgabe
 173   printf(" sorted array = ");
 174   for(i = 0; i < len - 1; i++) {
 175     printf(" %d,", b[i]);
 176   }
 177   if (len > 0) {
 178     printf(" %d\n", b[len - 1]);
 179   }
 180   return 0;
 181 }