Ein häufig verwendeter Algorithmus ist Quicksort da seine Implemtierung nicht allzu schwer
ist. Quicksort funktioniert nach dem Prinzip Teile und Herrsche. Also Rekursiv. Es wird
immer die Datei in 2 Teilen zerlegt und wieder sortiert. Die 2 Teile werden wiederum jeweils
in 2 Teilen zerlegt und sortiert usw.... bis die Datei sortiert ist. Die Rekursion beendet sich, wenn das Teilstück aus nur noch einem Element besteht.
Hier das Prinzip von Quicksort bildlich (Bildquelle : www.iti.fh-flensburg.de)....
- a.)Beste Fall
- b.)mittelbester Fall
- c.)im schlechtesten Fall
Hier der Quellcode zum Quicksort.............
/*Download:quick.c*/ #include <stdio.h> #include <time.h> #define MAX 5000 /*Unser Array zum sortieren*/ int test_array[MAX]; void init_test_array() { int i,j; for(i=MAX,j=0; i>=0; i--,j++){ test_array[j]=i; } } void quicksort(int array[], int links, int rechts) { int v,i,j,temp; if(rechts > links) { v=array[rechts]; i=links-1; j =rechts; for(;;) { while(array[++i] < v); while(array[--j] > v); if(i >= j) break; temp=array[i]; array[i]=array[j]; array[j]=temp; } temp=array[i]; array[i]=array[rechts]; array[rechts]=temp; quicksort(array, 1, i-1); quicksort(array, i+1, rechts); } } int main() { int i; float zeit; clock_t start, ende; /*Quicksort Laufzeittest*/ init_test_array(); start = clock(); quicksort(test_array, 1, MAX-1); ende = clock(); /*Ergebniss der Laufzeitmessung in Sekunden*/ zeit = (float)(ende-start) / (float)CLOCKS_PER_SEC; printf("Die Laufzeitmessung mit Quicksort ergab %.2f Sekunden\n",zeit); return 0; } |
Bei mir dauert es sage und schreibe 70 Sekunden bis diese lächerlichen 5000 Elemente
sortiert waren! Einfach gesagt, diese Implemtierung des Quicksort ist eine Zeitverschwendung in diesem Beispiel und stellt natürlich auch den schlechtesten Fall
da.
Man könnte nun versuchen den Algorithmus zu optimieren. Beispielsweise das break entfernen und
die Rekursion auflösen. Ein Beispiel dazu kann man in dem Buch "Algorithmen in C" von Robert
Sedgewick finden.
Nur stellt dabei die Frage, ob sich der Aufwand überhaupt lohnt, oder man nicht lieber doch
einen anderen schnelleren oder einfacheren Algorithmus zu verwenden zur Sicherheit.
Es kommt noch hinzu das nicht alle Quicksort Algorithmen stabil sind. Und was bringt es wenn
man eine Datei von 1 Millionen Elementen mit einer Sortierzeit von ein paar Wochen rechnen kann.
Für kleine Zufallsdaten oder bereits etwas sortiertere Daten mag Quicksort ganz gut geeignet seine und seine Arbeit gut machen, aber ansonsten empfehle ich Ihnen sich einen anderen Algorithmus zu verwenden.
