/**
* Heapsort-Algorithmus laut Vorlesung.
*/
-/** Array mit Heap */
-int *a;
/** Größe des Heaps */
-int N;
+static int N;
/**
* Tauscht die Elemente a[i] und a[j].
*/
-void exchange(int i,int j) {
- int v;
- v = a[i];
- a[i] = a[j];
- a[j] = v;
+static void exchange(int *a, int i, int j) {
+ int v;
+ v = a[i];
+ a[i] = a[j];
+ a[j] = v;
}
/**
* Läßt a[k] im Feld aufsteigen.
*/
-void upheap(int k) {
- while ((k > 1) && (a[k] < a[k / 2])) {
- exchange(k, k / 2);
- k = k / 2;
- }
+static void upheap(int *a, int k) {
+ while ((k > 0) && (a[k] < a[k / 2])) {
+ exchange(a, k, k / 2);
+ k = k / 2;
+ }
}
/**
* Fügt das neue Element v in den Heap der Größe N
* ein und erhöht N um 1
*/
-void insert(int v) {
- N++;
- a[N] = v;
- upheap(N);
+static void insert(int *a, int v) {
+ a[N] = v;
+ upheap(a, N);
+ N++;
}
/**
* Läßt a[k] im Feld versickern.
*/
-void downheap(int k) {
- int j = 2 * k;
- if (j < N) { // a[k] hat linken Sohn a[j]
- if (j + 1 < N) // a[k] hat auch rechten Sohn a[j+1]
- if (a[j] > a[j + 1])
- j++; // Jetzt ist a[j] der kleinere Sohn von a[k]
- if (a[k] > a[j]) {
- exchange(k, j);
- downheap(j);
- }
- }
+static void downheap(int *a, int k) {
+ int j = 2 * k;
+ if (j < N) { // a[k] hat linken Sohn a[j]
+ if (j + 1 < N) // a[k] hat auch rechten Sohn a[j+1]
+ if (a[j] > a[j + 1])
+ j++; // Jetzt ist a[j] der kleinere Sohn von a[k]
+ if (a[k] > a[j]) {
+ exchange(a, k, j);
+ downheap(a, j);
+ }
+ }
}
/**
* Liefert als Resultat das Heap-Element a[k], entfernt a[k]
* aus dem Heap und stellt die Heap-Eigenschaft wieder her.
*/
-int removeh(int k) {
- int v = a[k];
- a[k] = a[N];
- N--;
- if ((k > 1) && (a[k] < a[k / 2]))
- upheap(k);
- else
- downheap(k);
- return v;
+static int removeh(int *a, int k) {
+ int v = a[k];
+ a[k] = a[--N];
+ if ((k > 0) && (a[k] < a[k / 2]))
+ upheap(a, k);
+ else
+ downheap(a, k);
+
+ return v;
}
/**
* Aufbau des Heaps durch downheap.
*/
-void heapaufbau1(void) {
- int k;
+static void heapaufbau1(int *a) {
+ int k;
- for (k = N / 2; k >= 1; k--)
- downheap(k);
+ for (k = N / 2; k >= 1; k--)
+ downheap(a, k);
}
/**
* Aufbau des Heaps durch insert.
*/
-void heapaufbau2(void) {
- int k, m = N; N = 0;
- for (k = 1;k <= m; k++)
- insert(a[k]);
+static void heapaufbau2(int *a, int *b, int len) {
+ int k;
+ N = 0;
+ for (k = 0; k < len; ++k)
+ insert(a, b[k]);
}
/**
* Sortiert das gegebene Feld b mit den oben angegebenen
* Heap-Methoden und gibt das sortierte Feld zurück.
*/
-int *heapsort(int *b, int len) {
- int i, k;
- int *c;
-
- // Globale Variablen für die Heap-Methoden setzen
- a = (void *)malloc(sizeof(*a) * (len + 1));
- N = len;
-
- // Die Heap-Methoden arbeiten auf dem Bereich a[1],...,a[N],
- // normale Java-Array belegen aber b[0],...,b[b.length-1].
- for (i = 0; i < len; i++) {
- a[i + 1] = b[i];
- }
- heapaufbau2();
- // Ergebnis in c kopieren
- c = (void *)malloc(sizeof(*c) * len);
- for (k = 0; k < len; k++)
- c[k] = removeh(1);
- return c;
+static int *heapsort_(int *b, int len) {
+ int k;
+ int *c;
+ int *a;
+
+ // Globale Variablen für die Heap-Methoden setzen
+ a = malloc(sizeof(a[0]) * len);
+ heapaufbau2(a, b, len);
+
+ // Ergebnis in c kopieren
+ c = malloc(sizeof(c[0]) * len);
+ for (k = 0; k < len; k++)
+ c[k] = removeh(a, 0);
+
+ return c;
+}
+
+static int verify(int* fld, int count) {
+ int i;
+ int last = fld[0];
+ for(i = 1; i < count; ++i) {
+ if(fld[i] < last)
+ return 0;
+ last = fld[i];
+ }
+
+ return 1;
}
/**
* </pre>
*/
int main (int argc, char *argv[]) {
- // Umwandeln der Argumente in Zahlen
- int *b;
- int i, len;
-
- printf("Heap.c\n");
-
- len = argc - 1;
- b = (void *)malloc(len * sizeof(*b));
-
- for(i = 0; i < argc-1; i++) {
- b[i] = atoi(argv[i+1]);
- printf(" %d\n", b[i]);
- }
-
- if (len < 1) {
- printf("Usage: HeapSort <list of numbers>\n");
- printf("Continuing with default input.\n");
- // b = new int[] {3, 18, 5, 99, 104, 2};
- b = (void *)malloc(sizeof(*b) * (len = 6));
- b[0] = 3; b[1] = 18; b[2] = 5; b[3] = 99; b[4] = 104; b[5] = 2;
- }
-
- // Ausgabe
- //System.out.print("array={");
- // printf("length of array to sort: %d -- first element b[0]: %d\n", len, b[0]);
- printf(" array = ");
- for(i = 0; i < len - 1; i++) {
- printf(" %d,", b[i]);
- }
- if (len > 0) {
- printf(" %d\n", b[len - 1]);
- }
- // Sortieren
- b = heapsort(b, len);
-
- // Ausgabe
- printf(" sorted array = ");
- for(i = 0; i < len - 1; i++) {
- printf(" %d,", b[i]);
- }
- if (len > 0) {
- printf(" %d\n", b[len - 1]);
- }
- return 0;
+ // Umwandeln der Argumente in Zahlen
+ int *b;
+ int i, count, seed;
+
+ printf("Heap.c\n");
+
+ if(argc > 1)
+ count = atoi(argv[1]);
+ else
+ count = 10000;
+
+ if(argc > 2)
+ seed = atoi(argv[2]);
+ else
+ seed = 123456;
+
+ srand(seed);
+
+ b = (void*) malloc(sizeof(b[0]) * count);
+ for(i = 0; i < count; ++i)
+ b[i] = rand();
+
+ printf("Sorting %d random numbers (seed %d)\n",
+ count, seed);
+
+ // Sortieren
+ b = heapsort_(b, count);
+
+ printf("Sorted.\n");
+
+ if(verify(b, count))
+ printf("Verify succeeded.\n");
+ else
+ printf("Verify failed.\n");
+
+ return 0;
}
projects / libfirm / blobdiff