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 //------------------------------
  66 // Hauptfunktion des Programmes
  67 //------------------------------
  68 int main(int argc, char *argv[]) {
  69   int i, *fld;
  70   int len = argc - 1;
  71
  72   printf("QuickSort.c\n");
  73
  74   if (len <= 0) {
  75       printf("Usage: QuickSort <list of numbers>\n");
  76       printf("Continuing with default input.\n");
  77       // fld = new int[] {3, 18, 5, 99, 104, 2};
  78       fld = (void *)malloc(sizeof(*fld) * (len = 6));
  79       fld[0] = 3; fld[1] = 18; fld[2] = 5; fld[3] = 99; fld[4] = 104; fld[5] = 2;
  80   }
  81   else {
  82     // Speicher fuer fld erzeugen
  83     fld = (void *)malloc(sizeof(*fld) * len);
  84
  85     // Feldelemente belegen
  86     for( i = 0; i < len; i++ )
  87       fld[i] = atoi(argv[i + 1]);
  88   }
  89
  90   printf("array:  ");
  91   for(i = 0; i < len; i++) {
  92     printf("%d, ", fld[i]);
  93   }
  94
  95   // Sortieren
  96   bewegungen = 0;
  97   vergleiche = 0;
  98   quicksort( fld, 0, len - 1 );
  99
 100   // Ausgabe
 101   printf( "\nSorted: " );
 102
 103   for( i = 0; i < len; i++ ) {
 104     printf("%d, ", fld[i]);
 105   }
 106
 107   printf("\nNeeded %d comparisons and %d moves.\n", vergleiche, bewegungen);
 108
 109   return 0;
 110 }