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