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.
23 /** Größe des Heaps */
27 * Tauscht die Elemente a[i] und a[j].
29 void exchange(int i,int j) {
37 * Läßt a[k] im Feld aufsteigen.
40 while ((k > 0) && (a[k] < a[k / 2])) {
47 * Fügt das neue Element v in den Heap der Größe N
48 * ein und erhöht N um 1
57 * Läßt a[k] im Feld versickern.
59 void downheap(int 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]
64 j++; // Jetzt ist a[j] der kleinere Sohn von a[k]
73 * Liefert als Resultat das Heap-Element a[k], entfernt a[k]
74 * aus dem Heap und stellt die Heap-Eigenschaft wieder her.
79 if ((k > 0) && (a[k] < a[k / 2]))
87 * Aufbau des Heaps durch downheap.
89 void heapaufbau1(void) {
92 for (k = N / 2; k >= 1; k--)
97 * Aufbau des Heaps durch insert.
99 void heapaufbau2(int *b, int len) {
102 for (k = 0; k < len; ++k)
107 * Sortiert das gegebene Feld b mit den oben angegebenen
108 * Heap-Methoden und gibt das sortierte Feld zurück.
110 int *heapsort(int *b, int len) {
114 // Globale Variablen für die Heap-Methoden setzen
115 a = (void *)malloc(sizeof(*a) * len);
118 // Ergebnis in c kopieren
119 c = (void *)malloc(sizeof(*c) * len);
120 for (k = 0; k < len; k++)
126 * Ein einfaches Beispielprogramm. Alle Argumente des Programms müssen
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}
134 int main (int argc, char *argv[]) {
135 // Umwandeln der Argumente in Zahlen
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");
148 len = sizeof(_b)/sizeof(_b[0]);
151 b = (void *)malloc(len * sizeof(*b));
153 for(i = 0; i < argc-1; i++) {
154 b[i] = atoi(argv[i+1]);
155 printf(" %d\n", b[i]);
160 //System.out.print("array={");
161 // printf("length of array to sort: %d -- first element b[0]: %d\n", len, b[0]);
163 for(i = 0; i < len - 1; i++) {
164 printf(" %d,", b[i]);
167 printf(" %d\n", b[len - 1]);
170 b = heapsort(b, len);
173 printf(" sorted array = ");
174 for(i = 0; i < len - 1; i++) {
175 printf(" %d,", b[i]);
178 printf(" %d\n", b[len - 1]);