X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Ftest%2FQuickSort.c;h=2bcedfca9fe20429acbc12fa48c8ee685008bd12;hb=cc7725b3c4521e7a5116d73b095e0b3bcd5a2215;hp=526f806bf0e1fa3ec5bf53e58c0f7bbf479ecdab;hpb=e4691fe2e5046a9b2ae912e23e92ddcdcd2bb6e9;p=libfirm

diff --git a/ir/be/test/QuickSort.c b/ir/be/test/QuickSort.c
index 526f806bf..2bcedfca9 100644
--- a/ir/be/test/QuickSort.c
+++ b/ir/be/test/QuickSort.c
@@ -10,56 +10,88 @@
  * Licence:
  * URL:         http://www-info1.informatik.uni-wuerzburg.de/staff/wolf/teaching/pi1_ws98/java/QuickSort.java
  */
-
+#include <stdio.h>
 #include <stdlib.h>
 
+//#define COUNTACTIONS
+
+#ifdef COUNTACTIONS
 // Variablen, in denen die Bewegungen und Vergleiche gespeichert werden
-static int bewegungen;
-static int vergleiche;
+static int bewegungen = 0;
+static int vergleiche = 0;
+#endif
 
 
 //--------------------
 // quicksort-Funktion
 //--------------------
 static void quicksort(int *fld, int l, int r ) {
-  // Wenn der zu sortierende Teil eine Laenge <= 1 hat -> fertig
-  if( l < r ) {
-    int pivot = fld[r];
-    int i = l-1, j = r;
-    int v;
-
-    // mit dem Pivotelement sortieren
-    while( 1 ) {
-      while( fld[++i] < pivot )
-	vergleiche++;
-      vergleiche++;
-
-      while( j > l && fld[--j] > pivot )
-	vergleiche++;
-      vergleiche++;
-      // Wenn j <= i ist, wurde der zu sortierende Teil des Feldes
-      // durchlaufen -> fertig
-      if( j <= i )
-	break;
-
-      // Elemente tauschen
-      v = fld[i];
-      fld[i] = fld[j];
-      fld[j] = v;
-      // ein Tausch zweier Feldelemente wird als eine Bewegung gerechnet
-      bewegungen++;
-    }
-
-    // Pivotelement in die Mitte tauschen
-    fld[r] = fld[i];
-    fld[i] = pivot;
+	// Wenn der zu sortierende Teil eine Laenge <= 1 hat -> fertig
+	if( l >= r )
+		return;
+
+	int pivot = fld[r];
+	int i = l-1, j = r;
+	int v;
+
+	// mit dem Pivotelement sortieren
+	while( 1 ) {
+		while( fld[++i] < pivot ) {
+#ifdef COUNTACTIONS
+			vergleiche++;
+#endif
+		}
+#ifdef COUNTACTIONS
+		vergleiche++;
+#endif
+
+		while( j > l && fld[--j] > pivot ) {
+#ifdef COUNTACTIONS
+			vergleiche++;
+#endif
+		}
+
+#ifdef COUNTACTIONS
+		vergleiche++;
+#endif
+		// Wenn j <= i ist, wurde der zu sortierende Teil des Feldes
+		// durchlaufen -> fertig
+		if( j <= i )
+			break;
+
+		// Elemente tauschen
+		v = fld[i];
+		fld[i] = fld[j];
+		fld[j] = v;
+		// ein Tausch zweier Feldelemente wird als eine Bewegung gerechnet
+#ifdef COUNTACTIONS
+		bewegungen++;
+#endif
+	}
+
+	// Pivotelement in die Mitte tauschen
+	fld[r] = fld[i];
+	fld[i] = pivot;
+
+#ifdef COUNTACTIONS
+	bewegungen++;
+#endif
+
+	// Die zwei Teilfolgen rekursiv mit quicksort sortieren
+	quicksort( fld, l, i-1 );
+	quicksort( fld, i+1, r );
+}
 
-    bewegungen++;
+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];
+    }
 
-    // Die zwei Teilfolgen rekursiv mit quicksort sortieren
-    quicksort( fld, l, i-1 );
-    quicksort( fld, i+1, r );
-  }
+    return 1;
 }
 
 //------------------------------
@@ -67,44 +99,42 @@ static void quicksort(int *fld, int l, int r ) {
 //------------------------------
 int main(int argc, char *argv[]) {
   int i, *fld;
-  int len = argc - 1;
+  int count, seed;
 
   printf("QuickSort.c\n");
 
-  if (len <= 0) {
-      printf("Usage: QuickSort <list of numbers>\n");
-      printf("Continuing with default input.\n");
-      // fld = new int[] {3, 18, 5, 99, 104, 2};
-      fld = (void *)malloc(sizeof(*fld) * (len = 6));
-      fld[0] = 3; fld[1] = 18; fld[2] = 5; fld[3] = 99; fld[4] = 104; fld[5] = 2;
-  }
-  else {
-    // Speicher fuer fld erzeugen
-    fld = (void *)malloc(sizeof(*fld) * len);
-
-    // Feldelemente belegen
-    for( i = 0; i < len; i++ )
-      fld[i] = atoi(argv[i + 1]);
-  }
-
-  printf("array:  ");
-  for(i = 0; i < len; i++) {
-    printf("%d, ", fld[i]);
-  }
+  if(argc > 1)
+    count = atoi(argv[1]);
+  else
+    count = 10000;
 
-  // Sortieren
-  bewegungen = 0;
-  vergleiche = 0;
-  quicksort( fld, 0, len - 1 );
+  if(argc > 2)
+    seed = atoi(argv[2]);
+  else
+    seed = 123456;
 
-  // Ausgabe
-  printf( "\nSorted: " );
+  srand(seed);
 
-  for( i = 0; i < len; i++ ) {
-    printf("%d, ", fld[i]);
-  }
+  fld = (void*) malloc(sizeof(*fld) * count);
+  for(i = 0; i < count; ++i)
+      fld[i] = rand();
 
-  printf("\nNeeded %d comparisons and %d moves.\n", vergleiche, bewegungen);
+  printf("Sorting %d random numbers (seed %d)\n",
+          count, seed);
+  // Sortieren
+  quicksort(fld, 0, count-1);
+
+  // Ausgabe
+#ifdef COUNTACTIONS
+  printf("Sorted. (needed %d comparisons and %d moves.\n", vergleiche, bewegungen);
+#else
+  printf("Sorted.\n");
+#endif
+
+  if(verify(fld, count))
+      printf("Verify succeeded.\n");
+  else
+      printf("Verify failed.\n");
 
   return 0;
 }