3 * File name: test/HeapSort.java
4 * Purpose: sorting with heapsort
6 * Modified by: Michael Beck (for GCC-firm)
9 * Copyright: (c) 2003 Universitaet Karlsruhe
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
19 * Heapsort-Algorithmus laut Vorlesung.
21 /** Größe des Heaps */
25 * Tauscht die Elemente a[i] und a[j].
27 void exchange(int *a, int i, int j) {
35 * Läßt a[k] im Feld aufsteigen.
37 void upheap(int *a, int k) {
38 while ((k > 0) && (a[k] < a[k / 2])) {
39 exchange(a, k, k / 2);
45 * Fügt das neue Element v in den Heap der Größe N
46 * ein und erhöht N um 1
48 void insert(int *a, int v) {
55 * Läßt a[k] im Feld versickern.
57 void downheap(int *a, int 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]
62 j++; // Jetzt ist a[j] der kleinere Sohn von a[k]
71 * Liefert als Resultat das Heap-Element a[k], entfernt a[k]
72 * aus dem Heap und stellt die Heap-Eigenschaft wieder her.
74 int removeh(int *a, int k) {
77 if ((k > 0) && (a[k] < a[k / 2]))
86 * Aufbau des Heaps durch downheap.
88 void heapaufbau1(int *a) {
91 for (k = N / 2; k >= 1; k--)
96 * Aufbau des Heaps durch insert.
98 void heapaufbau2(int *a, int *b, int len) {
101 for (k = 0; k < len; ++k)
106 * Sortiert das gegebene Feld b mit den oben angegebenen
107 * Heap-Methoden und gibt das sortierte Feld zurück.
109 int *heapsort(int *b, int len) {
114 // Globale Variablen für die Heap-Methoden setzen
115 a = malloc(sizeof(a[0]) * len);
116 heapaufbau2(a, b, len);
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);
126 int verify(int* fld, int count) {
129 for(i = 1; i < count; ++i) {
139 * Ein einfaches Beispielprogramm. Alle Argumente des Programms müssen
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}
147 int main (int argc, char *argv[]) {
148 // Umwandeln der Argumente in Zahlen
155 count = atoi(argv[1]);
160 seed = atoi(argv[2]);
166 b = (void*) malloc(sizeof(b[0]) * count);
167 for(i = 0; i < count; ++i)
170 printf("Sorting %d random numbers (seed %d)\n",
174 b = heapsort(b, count);
179 printf("Verify succeeded.\n");
181 printf("Verify failed.\n");