nsz Git - libfirm/blob - ir/be/test/QuickSort.c

   1 /*
   2  * Project:     GCC-firm
   3  * File name:   test/Quicksort.c
   4  * Purpose:     sorting with quicksort
   5  * Author:
   6  * Modified by: Michael Beck (for GCC-firm)
   7  * Created:     XX.11.2001
   8  * CVS-ID:      $Id$
   9  * Copyright:   (c) 2001 Universitaet Karlsruhe
  10  * Licence:
  11  * URL:         http://www-info1.informatik.uni-wuerzburg.de/staff/wolf/teaching/pi1_ws98/java/QuickSort.java
  12  */
  13
  14 #include <stdlib.h>
  15
  16 // Variablen, in denen die Bewegungen und Vergleiche gespeichert werden
  17 static int bewegungen;
  18 static int vergleiche;
  19
  20
  21 //--------------------
  22 // quicksort-Funktion
  23 //--------------------
  24 static void quicksort(int *fld, int l, int r ) {
  25   // Wenn der zu sortierende Teil eine Laenge <= 1 hat -> fertig
  26   if( l < r ) {
  27     int pivot = fld[r];
  28     int i = l-1, j = r;
  29     int v;
  30
  31     // mit dem Pivotelement sortieren
  32     while( 1 ) {
  33       while( fld[++i] < pivot )
  34         vergleiche++;
  35       vergleiche++;
  36
  37       while( j > l && fld[--j] > pivot )
  38         vergleiche++;
  39       vergleiche++;
  40       // Wenn j <= i ist, wurde der zu sortierende Teil des Feldes
  41       // durchlaufen -> fertig
  42       if( j <= i )
  43         break;
  44
  45       // Elemente tauschen
  46       v = fld[i];
  47       fld[i] = fld[j];
  48       fld[j] = v;
  49       // ein Tausch zweier Feldelemente wird als eine Bewegung gerechnet
  50       bewegungen++;
  51     }
  52
  53     // Pivotelement in die Mitte tauschen
  54     fld[r] = fld[i];
  55     fld[i] = pivot;
  56
  57     bewegungen++;
  58
  59     // Die zwei Teilfolgen rekursiv mit quicksort sortieren
  60     quicksort( fld, l, i-1 );
  61     quicksort( fld, i+1, r );
  62   }
  63 }
  64
  65 int verify(int* fld, int count) {
  66     int i;
  67     int last = fld[0];
  68     for(i = 1; i < count; ++i) {
  69         if(fld[i] < last)
  70             return 0;
  71         last = fld[i];
  72     }
  73
  74     return 1;
  75 }
  76
  77 //------------------------------
  78 // Hauptfunktion des Programmes
  79 //------------------------------
  80 int main(int argc, char *argv[]) {
  81   int i, *fld;
  82   int count, seed;
  83
  84   printf("QuickSort.c\n");
  85
  86   if(argc > 1)
  87     count = atoi(argv[1]);
  88   else
  89     count = 10000;
  90
  91   if(argc > 2)
  92     seed = atoi(argv[2]);
  93   else
  94     seed = 123456;
  95
  96   srand(seed);
  97
  98   fld = (void*) malloc(sizeof(*fld) * count);
  99   for(i = 0; i < count; ++i)
 100       fld[i] = rand();
 101
 102   printf("Sorting %d random numbers (seed %d)\n",
 103           count, seed);
 104   // Sortieren
 105   bewegungen = 0;
 106   vergleiche = 0;
 107   quicksort(fld, 0, count-1);
 108
 109   // Ausgabe
 110   printf("Sorted. (needed %d comparisons and %d moves.\n", vergleiche, bewegungen);
 111
 112   // TODO verify
 113   if(verify(fld, count))
 114       printf("Verify succeeded.\n");
 115   else
 116       printf("Verify failed.\n");
 117
 118   return 0;
 119 }