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 > 1) && (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.
80 if ((k > 1) && (a[k] < a[k / 2]))
88 * Aufbau des Heaps durch downheap.
90 void heapaufbau1(void) {
93 for (k = N / 2; k >= 1; k--)
98 * Aufbau des Heaps durch insert.
100 void heapaufbau2(void) {
102 for (k = 1;k <= m; 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 + 1));
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++) {
124 // Ergebnis in c kopieren
125 c = (void *)malloc(sizeof(*c) * len);
126 for (k = 0; k < len; k++)
132 * Ein einfaches Beispielprogramm. Alle Argumente des Programms müssen
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}
140 int main (int argc, char *argv[]) {
141 // Umwandeln der Argumente in Zahlen
148 b = (void *)malloc(len * sizeof(*b));
150 for(i = 0; i < argc-1; i++) {
151 b[i] = atoi(argv[i+1]);
152 printf(" %d\n", b[i]);
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;
164 //System.out.print("array={");
165 // printf("length of array to sort: %d -- first element b[0]: %d\n", len, b[0]);
167 for(i = 0; i < len - 1; i++) {
168 printf(" %d,", b[i]);
171 printf(" %d\n", b[len - 1]);
174 b = heapsort(b, len);
177 printf(" sorted array = ");
178 for(i = 0; i < len - 1; i++) {
179 printf(" %d,", b[i]);
182 printf(" %d\n", b[len - 1]);