X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Ftest%2FHeapSort.c;h=3879b7801c8041fa06357fef24439d785149a163;hb=4032a5c080d6801aacbc352b650f8ca28edf0248;hp=723982cb0dbb903864a355bc70efdc1a1676a455;hpb=e2a3f3ce6713dee040699cd38ee162c62e8aef22;p=libfirm

diff --git a/ir/be/test/HeapSort.c b/ir/be/test/HeapSort.c
index 723982cb0..3879b7801 100644
--- a/ir/be/test/HeapSort.c
+++ b/ir/be/test/HeapSort.c
@@ -18,89 +18,88 @@
 /**
  * Heapsort-Algorithmus laut Vorlesung.
  */
-/** Array mit Heap */
-int *a;
 /** Größe des Heaps */
 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;
+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 > 0) && (a[k] < a[k / 2])) {
-    exchange(k, k / 2);
-    k = k / 2;
-  }
+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) {
-  a[N] = v;
-  upheap(N);
-  N++;
+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);
-    }
-  }
+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];
-  if ((k > 0) && (a[k] < a[k / 2]))
-    upheap(k);
-  else
-    downheap(k);
-  return v;
+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;
+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(int *b, int len) {
-  int k;
-  N = 0;
-  for (k = 0; k < len; ++k)
-    insert(b[k]);
+void heapaufbau2(int *a, int *b, int len) {
+	int k;
+	N = 0;
+	for (k = 0; k < len; ++k)
+		insert(a, b[k]);
 }
 
 /**
@@ -108,18 +107,32 @@ void heapaufbau2(int *b, int len) {
  * 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);
-  heapaufbau2(b, len);
-
-  // Ergebnis in c kopieren
-  c = (void *)malloc(sizeof(*c) * len);
-  for (k = 0; k < len; k++)
-    c[k] = removeh(0);
-  return c;
+	int i, 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;
+}
+
+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;
 }
 
 /**
@@ -132,50 +145,40 @@ int *heapsort(int *b, int len) {
  * </pre>
  */
 int main (int argc, char *argv[]) {
-  // Umwandeln der Argumente in Zahlen
-  int *b;
-  int i, len;
-
-  printf("Heap.c\n");
-
-  len = argc - 1;
-
-  if (len < 1) {
-      static int _b[] = {3, 18, 5, 99, 104, 2};
-      printf("Usage: HeapSort <list of numbers>\n");
-      printf("Continuing with default input.\n");
-      b = _b;
-      len = sizeof(_b)/sizeof(_b[0]);
-  }
-  else {
-    b = (void *)malloc(len * sizeof(*b));
-
-    for(i = 0; i < argc-1; i++) {
-      b[i] = atoi(argv[i+1]);
-      printf(" %d\n", b[i]);
-    }
-  }
-
-  // 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;
 }