X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Ftest%2FHeapSort.c;h=5d82040740e55985f9a755b4faab4f24fd1ee59d;hb=3c6b9f272fd0d2b2c48a1e34084411c179d08105;hp=1b7e4e9b2ca0600d3b82d150e6ab63b3f7c11670;hpb=e4691fe2e5046a9b2ae912e23e92ddcdcd2bb6e9;p=libfirm

diff --git a/ir/be/test/HeapSort.c b/ir/be/test/HeapSort.c
index 1b7e4e9b2..5d8204074 100644
--- a/ir/be/test/HeapSort.c
+++ b/ir/be/test/HeapSort.c
@@ -18,114 +18,121 @@
 /**
  * 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;
 }
 
 /**
@@ -138,48 +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;
-  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;
 }