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 /** Größe des Heaps */
  22 static int N;
  23
  24 /**
  25  * Tauscht die Elemente a[i] und a[j].
  26  */
  27 static void exchange(int *a, int i, int j) {
  28         int v;
  29         v = a[i];
  30         a[i] = a[j];
  31         a[j] = v;
  32 }
  33
  34 /**
  35  * Läßt a[k] im Feld aufsteigen.
  36  */
  37 static void upheap(int *a, int k) {
  38         while ((k > 0) && (a[k] < a[k / 2])) {
  39                 exchange(a, k, k / 2);
  40                 k = k / 2;
  41         }
  42 }
  43
  44 /**
  45  * Fügt das neue Element v in den Heap der Größe N
  46  * ein und erhöht N um 1
  47  */
  48 static void insert(int *a, int v) {
  49         a[N] = v;
  50         upheap(a, N);
  51         N++;
  52 }
  53
  54 /**
  55 * Läßt a[k] im Feld versickern.
  56 */
  57 static void downheap(int *a, int k) {
  58         int j = 2 * k;
  59         if (j < N) {    // a[k] hat linken Sohn a[j]
  60                 if (j + 1 < N)   // a[k] hat auch rechten Sohn a[j+1]
  61                         if (a[j] > a[j + 1])
  62                                 j++;        // Jetzt ist a[j] der kleinere Sohn von a[k]
  63                 if (a[k] > a[j]) {
  64                         exchange(a, k, j);
  65                         downheap(a, j);
  66                 }
  67         }
  68 }
  69
  70 /**
  71  * Liefert als Resultat das Heap-Element a[k], entfernt a[k]
  72  * aus dem Heap und stellt die Heap-Eigenschaft wieder her.
  73  */
  74 static int removeh(int *a, int k) {
  75         int v = a[k];
  76         a[k] = a[--N];
  77         if ((k > 0) && (a[k] < a[k / 2]))
  78                 upheap(a, k);
  79         else
  80                 downheap(a, k);
  81
  82         return v;
  83 }
  84
  85 /**
  86  * Aufbau des Heaps durch downheap.
  87  */
  88 static void heapaufbau1(int *a) {
  89         int k;
  90
  91         for (k = N / 2; k >= 1; k--)
  92                 downheap(a, k);
  93 }
  94
  95 /**
  96  * Aufbau des Heaps durch insert.
  97  */
  98 static void heapaufbau2(int *a, int *b, int len) {
  99         int k;
 100         N = 0;
 101         for (k = 0; k < len; ++k)
 102                 insert(a, b[k]);
 103 }
 104
 105 /**
 106  * Sortiert das gegebene Feld b mit den oben angegebenen
 107  * Heap-Methoden und gibt das sortierte Feld zurück.
 108  */
 109 static int *heapsort_(int *b, int len) {
 110         int k;
 111         int *c;
 112         int *a;
 113
 114         // Globale Variablen für die Heap-Methoden setzen
 115         a = malloc(sizeof(a[0]) * len);
 116         heapaufbau2(a, b, len);
 117
 118         // Ergebnis in c kopieren
 119         c = malloc(sizeof(c[0]) * len);
 120         for (k = 0; k < len; k++)
 121                 c[k] = removeh(a, 0);
 122
 123         return c;
 124 }
 125
 126 static int verify(int* fld, int count) {
 127     int i;
 128     int last = fld[0];
 129     for(i = 1; i < count; ++i) {
 130         if(fld[i] < last)
 131             return 0;
 132         last = fld[i];
 133     }
 134
 135     return 1;
 136 }
 137
 138 /**
 139  * Ein einfaches Beispielprogramm. Alle Argumente des Programms müssen
 140  * Zahlen sein.
 141  * Bsp:<pre>
 142  * java Heapsort 6 13 17 42 9 3 5
 143  * array={6,13,17,42,9,3,5}
 144  * sorted array={3,5,6,9,13,17,42}
 145  * </pre>
 146  */
 147 int main (int argc, char *argv[]) {
 148         // Umwandeln der Argumente in Zahlen
 149         int *b;
 150         int i, count, seed;
 151
 152         printf("Heap.c\n");
 153
 154         if(argc > 1)
 155                 count = atoi(argv[1]);
 156         else
 157                 count = 10000;
 158
 159         if(argc > 2)
 160                 seed = atoi(argv[2]);
 161         else
 162                 seed = 123456;
 163
 164         srand(seed);
 165
 166         b = (void*) malloc(sizeof(b[0]) * count);
 167         for(i = 0; i < count; ++i)
 168                 b[i] = rand();
 169
 170         printf("Sorting %d random numbers (seed %d)\n",
 171           count, seed);
 172
 173         // Sortieren
 174         b = heapsort_(b, count);
 175
 176         printf("Sorted.\n");
 177
 178         if(verify(b, count))
 179                 printf("Verify succeeded.\n");
 180         else
 181                 printf("Verify failed.\n");
 182
 183         return 0;
 184 }