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 > 1) && (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   N++;
  52   a[N] = v;
  53   upheap(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   N--;
  80   if ((k > 1) && (a[k] < a[k / 2]))
  81     upheap(k);
  82   else
  83     downheap(k);
  84   return v;
  85 }
  86
  87 /**
  88  * Aufbau des Heaps durch downheap.
  89  */
  90 void heapaufbau1(void) {
  91   int k;
  92
  93   for (k = N / 2; k >= 1; k--)
  94     downheap(k);
  95 }
  96
  97 /**
  98  * Aufbau des Heaps durch insert.
  99  */
 100 void heapaufbau2(void) {
 101   int k, m = N; N = 0;
 102   for (k = 1;k <= m; k++)
 103     insert(a[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 + 1));
 116   N = len;
 117
 118   // Die Heap-Methoden arbeiten auf dem Bereich a[1],...,a[N],
 119   // normale Java-Array belegen aber b[0],...,b[b.length-1].
 120   for (i = 0; i < len; i++) {
 121     a[i + 1] = b[i];
 122   }
 123   heapaufbau2();
 124   // Ergebnis in c kopieren
 125   c = (void *)malloc(sizeof(*c) * len);
 126   for (k = 0; k < len; k++)
 127     c[k] = removeh(1);
 128   return c;
 129 }
 130
 131 /**
 132  * Ein einfaches Beispielprogramm. Alle Argumente des Programms müssen
 133  * Zahlen sein.
 134  * Bsp:<pre>
 135  * java Heapsort 6 13 17 42 9 3 5
 136  * array={6,13,17,42,9,3,5}
 137  * sorted array={3,5,6,9,13,17,42}
 138  * </pre>
 139  */
 140 int main (int argc, char *argv[]) {
 141   // Umwandeln der Argumente in Zahlen
 142   int *b;
 143   int i, len;
 144
 145   printf("Heap.c\n");
 146
 147   len = argc - 1;
 148   b = (void *)malloc(len * sizeof(*b));
 149
 150   for(i = 0; i < argc-1; i++) {
 151     b[i] = atoi(argv[i+1]);
 152     printf(" %d\n", b[i]);
 153   }
 154
 155   if (len < 1) {
 156       printf("Usage: HeapSort <list of numbers>\n");
 157       printf("Continuing with default input.\n");
 158       // b = new int[] {3, 18, 5, 99, 104, 2};
 159       b = (void *)malloc(sizeof(*b) * (len = 6));
 160       b[0] = 3; b[1] = 18; b[2] = 5; b[3] = 99; b[4] = 104; b[5] = 2;
 161   }
 162
 163   // Ausgabe
 164   //System.out.print("array={");
 165   // printf("length of array to sort: %d -- first element b[0]: %d\n", len, b[0]);
 166   printf(" array = ");
 167   for(i = 0; i < len - 1; i++) {
 168     printf(" %d,", b[i]);
 169   }
 170   if (len > 0) {
 171     printf(" %d\n", b[len - 1]);
 172   }
 173   // Sortieren
 174   b = heapsort(b, len);
 175
 176   // Ausgabe
 177   printf(" sorted array = ");
 178   for(i = 0; i < len - 1; i++) {
 179     printf(" %d,", b[i]);
 180   }
 181   if (len > 0) {
 182     printf(" %d\n", b[len - 1]);
 183   }
 184   return 0;
 185 }