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
19 // Variablen, in denen die Bewegungen und Vergleiche gespeichert werden
20 static int bewegungen = 0;
21 static int vergleiche = 0;
25 //--------------------
27 //--------------------
28 static void quicksort(int *fld, int l, int r ) {
29 // Wenn der zu sortierende Teil eine Laenge <= 1 hat -> fertig
37 // mit dem Pivotelement sortieren
39 while( fld[++i] < pivot ) {
48 while( j > l && fld[--j] > pivot ) {
57 // Wenn j <= i ist, wurde der zu sortierende Teil des Feldes
58 // durchlaufen -> fertig
66 // ein Tausch zweier Feldelemente wird als eine Bewegung gerechnet
72 // Pivotelement in die Mitte tauschen
80 // Die zwei Teilfolgen rekursiv mit quicksort sortieren
81 quicksort( fld, l, i-1 );
82 quicksort( fld, i+1, r );
85 int verify(int* fld, int count) {
88 for(i = 1; i < count; ++i) {
97 //------------------------------
98 // Hauptfunktion des Programmes
99 //------------------------------
100 int main(int argc, char *argv[]) {
104 printf("QuickSort.c\n");
107 count = atoi(argv[1]);
112 seed = atoi(argv[2]);
118 fld = (void*) malloc(sizeof(*fld) * count);
119 for(i = 0; i < count; ++i)
122 printf("Sorting %d random numbers (seed %d)\n",
125 quicksort(fld, 0, count-1);
129 printf("Sorted. (needed %d comparisons and %d moves.\n", vergleiche, bewegungen);
134 if(verify(fld, count))
135 printf("Verify succeeded.\n");
137 printf("Verify failed.\n");