3 * File name: test/Quicksort.c
4 * Purpose: sorting with quicksort
6 * Modified by: Michael Beck (for GCC-firm)
9 * Copyright: (c) 2001 Universitaet Karlsruhe
11 * URL: http://www-info1.informatik.uni-wuerzburg.de/staff/wolf/teaching/pi1_ws98/java/QuickSort.java
16 // Variablen, in denen die Bewegungen und Vergleiche gespeichert werden
17 static int bewegungen;
18 static int vergleiche;
21 //--------------------
23 //--------------------
24 static void quicksort(int *fld, int l, int r ) {
25 // Wenn der zu sortierende Teil eine Laenge <= 1 hat -> fertig
31 // mit dem Pivotelement sortieren
33 while( fld[++i] < pivot )
37 while( j > l && fld[--j] > pivot )
40 // Wenn j <= i ist, wurde der zu sortierende Teil des Feldes
41 // durchlaufen -> fertig
49 // ein Tausch zweier Feldelemente wird als eine Bewegung gerechnet
53 // Pivotelement in die Mitte tauschen
59 // Die zwei Teilfolgen rekursiv mit quicksort sortieren
60 quicksort( fld, l, i-1 );
61 quicksort( fld, i+1, r );
65 //------------------------------
66 // Hauptfunktion des Programmes
67 //------------------------------
68 int main(int argc, char *argv[]) {
72 printf("QuickSort.c\n");
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;
82 // Speicher fuer fld erzeugen
83 fld = (void *)malloc(sizeof(*fld) * len);
85 // Feldelemente belegen
86 for( i = 0; i < len; i++ )
87 fld[i] = atoi(argv[i + 1]);
91 for(i = 0; i < len; i++) {
92 printf("%d, ", fld[i]);
98 quicksort( fld, 0, len - 1 );
101 printf( "\nSorted: " );
103 for( i = 0; i < len; i++ ) {
104 printf("%d, ", fld[i]);
107 printf("\nNeeded %d comparisons and %d moves.\n", vergleiche, bewegungen);