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
17 // Variablen, in denen die Bewegungen und Vergleiche gespeichert werden
18 static int bewegungen;
19 static int vergleiche;
22 //--------------------
24 //--------------------
25 static void quicksort(int *fld, int l, int r ) {
26 // Wenn der zu sortierende Teil eine Laenge <= 1 hat -> fertig
32 // mit dem Pivotelement sortieren
34 while( fld[++i] < pivot )
38 while( j > l && fld[--j] > pivot )
41 // Wenn j <= i ist, wurde der zu sortierende Teil des Feldes
42 // durchlaufen -> fertig
50 // ein Tausch zweier Feldelemente wird als eine Bewegung gerechnet
54 // Pivotelement in die Mitte tauschen
60 // Die zwei Teilfolgen rekursiv mit quicksort sortieren
61 quicksort( fld, l, i-1 );
62 quicksort( fld, i+1, r );
66 int verify(int* fld, int count) {
69 for(i = 1; i < count; ++i) {
78 //------------------------------
79 // Hauptfunktion des Programmes
80 //------------------------------
81 int main(int argc, char *argv[]) {
85 printf("QuickSort.c\n");
88 count = atoi(argv[1]);
99 fld = (void*) malloc(sizeof(*fld) * count);
100 for(i = 0; i < count; ++i)
103 printf("Sorting %d random numbers (seed %d)\n",
108 quicksort(fld, 0, count-1);
111 printf("Sorted. (needed %d comparisons and %d moves.\n", vergleiche, bewegungen);
114 if(verify(fld, count))
115 printf("Verify succeeded.\n");
117 printf("Verify failed.\n");