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 #include <stdio.h>
  14 #include <stdlib.h>
  15
  16 #define COUNTACTIONS
  17
  18 #ifdef COUNTACTIONS
  19 // Variablen, in denen die Bewegungen und Vergleiche gespeichert werden
  20 static int bewegungen = 0;
  21 static int vergleiche = 0;
  22 #endif
  23
  24
  25 //--------------------
  26 // quicksort-Funktion
  27 //--------------------
  28 static void quicksort(int *fld, int l, int r ) {
  29         // Wenn der zu sortierende Teil eine Laenge <= 1 hat -> fertig
  30         if( l >= r )
  31                 return;
  32
  33         int pivot = fld[r];
  34         int i = l-1, j = r;
  35         int v;
  36
  37         // mit dem Pivotelement sortieren
  38         while( 1 ) {
  39                 while( fld[++i] < pivot ) {
  40 #ifdef COUNTACTIONS
  41                         vergleiche++;
  42 #endif
  43                 }
  44 #ifdef COUNTACTIONS
  45                 vergleiche++;
  46 #endif
  47
  48                 while( j > l && fld[--j] > pivot ) {
  49 #ifdef COUNTACTIONS
  50                         vergleiche++;
  51 #endif
  52                 }
  53
  54 #ifdef COUNTACTIONS
  55                 vergleiche++;
  56 #endif
  57                 // Wenn j <= i ist, wurde der zu sortierende Teil des Feldes
  58                 // durchlaufen -> fertig
  59                 if( j <= i )
  60                         break;
  61
  62                 // Elemente tauschen
  63                 v = fld[i];
  64                 fld[i] = fld[j];
  65                 fld[j] = v;
  66                 // ein Tausch zweier Feldelemente wird als eine Bewegung gerechnet
  67 #ifdef COUNTACTIONS
  68                 bewegungen++;
  69 #endif
  70         }
  71
  72         // Pivotelement in die Mitte tauschen
  73         fld[r] = fld[i];
  74         fld[i] = pivot;
  75
  76 #ifdef COUNTACTIONS
  77         bewegungen++;
  78 #endif
  79
  80         // Die zwei Teilfolgen rekursiv mit quicksort sortieren
  81         quicksort( fld, l, i-1 );
  82         quicksort( fld, i+1, r );
  83 }
  84
  85 int verify(int* fld, int count) {
  86     int i;
  87     int last = fld[0];
  88     for(i = 1; i < count; ++i) {
  89         if(fld[i] < last)
  90             return 0;
  91         last = fld[i];
  92     }
  93
  94     return 1;
  95 }
  96
  97 //------------------------------
  98 // Hauptfunktion des Programmes
  99 //------------------------------
 100 int main(int argc, char *argv[]) {
 101   int i, *fld;
 102   int count, seed;
 103
 104   printf("QuickSort.c\n");
 105
 106   if(argc > 1)
 107     count = atoi(argv[1]);
 108   else
 109     count = 10000;
 110
 111   if(argc > 2)
 112     seed = atoi(argv[2]);
 113   else
 114     seed = 123456;
 115
 116   srand(seed);
 117
 118   fld = (void*) malloc(sizeof(*fld) * count);
 119   for(i = 0; i < count; ++i)
 120       fld[i] = rand();
 121
 122   printf("Sorting %d random numbers (seed %d)\n",
 123           count, seed);
 124   // Sortieren
 125   quicksort(fld, 0, count-1);
 126
 127   // Ausgabe
 128 #ifdef COUNTACTIONS
 129   printf("Sorted. (needed %d comparisons and %d moves.\n", vergleiche, bewegungen);
 130 #else
 131   printf("Sorted.\n");
 132 #endif
 133
 134   if(verify(fld, count))
 135       printf("Verify succeeded.\n");
 136   else
 137       printf("Verify failed.\n");
 138
 139   return 0;
 140 }