===== QuickSort ===== Der QuickSort-Algorithmus ist ein effizienter, rekursiv arbeitender Algorithmus, der sich als Standard für Sortierprobleme etabliert hat. Er arbeitet nach dem Divide-and-Conquer-Prinzip (Teile und Herrsche) und teilt die zu sortierende Liste immer wieder in zwei kleinere Teillisten auf. Dabei enthält die linke Teilliste jeweils nur Elemente, die kleiner als oder gleich einem Vergleichselement (Pivot-Element) sind und die rechte nur Elemente, die größer als oder gleich dem Pivot-Element sind. Der gleiche Algorithmus wird nun auf diese beiden kleineren Teillisten angewandt. Wenn am Ende die Teillisten nur noch genau ein Element enthalten, dann ist die Sortierung fertig. ===== Implementierung ===== ==== C ==== Eine Implementierung in C für int-Arrays. /// @param values Zeiger auf erste das Element des zu sortierenden Arrays /// @param left Linke Grenze des zu sortierenden "Teil-Arrays" /// @param right Rechte Grenze des zu sortierenden "Teil-Arrays" void QuickSort (int *values, size_t left, size_t right) { size_t i = left, j = right; // Zählindizes int pivot = values[ (left + right) >> 1 ]; // Pivot-Element (Array-Mitte) bestimmen int tmp; // Temporäre Variable zum Tauschen der Werte // Solange Paare suchen und tauschen, bis sich die Zählindizes "getroffen" haben do { // Paar finden, das getauscht werden muss while ( values[i] <= pivot ) ++i; while ( pivot <= values[j] ) --j; // Wenn sich die Zählindizes noch nicht "getroffen" haben, dann tauschen und weiterzählen // Sollten die Zählindizes gleich sein, dann zähle einfach weiter und unterbrich die Schleife if (i < j) { tmp = values[i]; values[i] = values[j]; values[j] = tmp; ++i; --j; } else if (i == j) { ++i; --j; break; } } while (i <= j); // Wenn die Teillisten mehr als ein Element enthalten, dann wende QuickSort auf sie an if (left < j) QuickSort(values, left, j); if (i < right) QuickSort(values, i, right); } ==== C++ ==== Eine Implementierung in C++ für Arrays beliebiger Datentypen, die den kleiner als-Operator unterstützen. // Tauschalgorithmus einbinden #include /// @param values Zeiger auf das erste Element des zu sortierenden Arrays /// @param left Linke Grenze des zu sortierenden "Teil-Arrays" /// @param right Rechte Grenze des zu sortierenden "Teil-Arrays" template< typename T > void QuickSort (T *values, size_t left, size_t right) { size_t i = left, j = right; // Zählindizes T pivot = values[ (left + right) >> 1 ]; // Pivot-Element (Array-Mitte) bestimmen // Solange Paare suchen und tauschen, bis sich die Zählindizes "getroffen" haben do { // Paar finden, dass getauscht werden muss while ( values[i] <= pivot ) ++i; while ( pivot <= values[j] ) --j; // Wenn sich die Zählindizes noch nicht "getroffen" haben, dann tauschen und weiterzählen // Sollten die Zählindizes gleich sein, dann zähle einfach weiter und unterbrich die Schleife if (i < j) { std::swap( values[i], values[j] ); ++i; --j; } else if (i == j) { ++i; --j; break; } } while (i <= j); // Wenn die Teillisten mehr als ein Element enthalten, dann wende QuickSort auf sie an if (left < j) QuickSort(values, left, j); if (i < right) QuickSort(values, i, right); } ==== Haskell ==== Eine Implementierung eines QuickSort-Algorithmus für eine Integerliste in Haskell: qs :: [Int] -> [Int] qs [] = [] qs (x:xs) = qs [y | y <- xs , y < x] ++ [x] ++ qs[y | y <- xs , y >= x] ===== Instabilität ===== QuickSort weist im Gegensatz zu vielen anderen Sortieralgorithmen eine Eigenschaft auf, die sich Instabilität nennt. Nach außen hin gleiche Elemente im Array behalten nach dem Sortieren nicht unbedingt ihre Ausgangsreihenfolge. Diese Eigenschaft kann ein Problem darstellen, wenn man strukturierte Daten nach verschiedenen Kriterien Sortieren will. Dies lässt sich am besten anhand eines Beispielcodes verdeutlichen; der hier dargestellte Code könnte ein Ausschnitt aus einer Verwaltungssoftware sein. // Funktionen printf, memcpy und strncpy einbinden #include #include // Legt fest, wie viele Zeichen eine Zeichenkette maximal haben soll #define STRING_LENGTH 32 // Struktur, in der relevante Daten zu Personen zusammengefasst werden struct Person { char Name[STRING_LENGTH]; // Nachname char Forename[STRING_LENGTH]; // Vorname }; // Sortiert ein Array von Personen nach Nachnamen /// @param persons Zeiger auf erste das Element des zu sortierenden Arrays /// @param left Linke Grenze des zu sortierenden "Teil-Arrays" /// @param right Rechte Grenze des zu sortierenden "Teil-Arrays" void QuickSort_Name (struct Person *persons, size_t left, size_t right) { size_t i = left, j = right; // Zählindizes char pivot[STRING_LENGTH]; // Pivotelement Person tmp; // Temporäre Variable zum Tauschen der Werte // Pivotelement bestimmen strncpy( pivot, persons[ (left + right) >> 1 ].Name, STRING_LENGTH ); // Solange Paare suchen und tauschen, bis sich die Zählindizes "getroffen" haben do { // Paar finden, dass getauscht werden muss while (strncmp( persons[i].Name, pivot, STRING_LENGTH ) <= 0) ++i; while (strncmp( pivot, persons[j].Name, STRING_LENGTH ) <= 0) --j; // Wenn sich die Zählindizes noch nicht "getroffen" haben, dann tauschen und weiterzählen // Sollten die Zählindizes gleich sein, dann zähle einfach weiter und unterbrich die Schleife if (i < j) { memcpy( &tmp, &persons[i], sizeof(struct Person) ); memcpy( &persons[i], &persons[j], sizeof(struct Person) ); memcpy( &persons[j], &tmp, sizeof(struct Person) ); ++i; --j; } else if (i == j) { ++i; --j; break; } } while (i <= j); // Wenn die Teillisten mehr als ein Element enthalten, dann wende QuickSort auf sie an if (left < j) QuickSort_Name(persons, left, j); if (i < right) QuickSort_Name(persons, i, right); } // Sortiert ein Array von Personen nach Vornamen /// @param persons Zeiger auf erste das Element des zu sortierenden Arrays /// @param left Linke Grenze des zu sortierenden "Teil-Arrays" /// @param right Rechte Grenze des zu sortierenden "Teil-Arrays" void QuickSort_Forename (struct Person *persons, size_t left, size_t right) { size_t i = left, j = right; // Zählindizes char pivot[STRING_LENGTH]; // Pivotelement Person tmp; // Temporäre Variable zum Tauschen der Werte // Pivotelement bestimmen strncpy( pivot, persons[ (left + right) >> 1 ].Forename, STRING_LENGTH ); // Solange Paare suchen und tauschen, bis sich die Zählindizes "getroffen" haben do { // Paar finden, dass getauscht werden muss while (strncmp( persons[i].Forename, pivot, STRING_LENGTH ) < 0) ++i; while (strncmp( pivot, persons[j].Forename, STRING_LENGTH ) < 0) --j; // Wenn sich die Zählindizes noch nicht "getroffen" haben, dann tauschen und weiterzählen // Sollten die Zählindizes gleich sein, dann zähle einfach weiter und unterbrich die Schleife if (i < j) { memcpy( &tmp, &persons[i], sizeof(struct Person) ); memcpy( &persons[i], &persons[j], sizeof(struct Person) ); memcpy( &persons[j], &tmp, sizeof(struct Person) ); ++i; --j; } else if (i == j) { ++i; --j; break; } } while (i <= j); // Wenn die Teillisten mehr als ein Element enthalten, dann wende QuickSort auf sie an if (left < j) QuickSort_Forename(persons, left, j); if (i < right) QuickSort_Forename(persons, i, right); } int main (void) { // Array für Personen anlegen und ausgeben struct Person persons[4]; strncpy( persons[0].Name, "Mueller", STRING_LENGTH ); strncpy( persons[0].Forename, "Heinrich", STRING_LENGTH ); strncpy( persons[1].Name, "Schulze", STRING_LENGTH ); strncpy( persons[1].Forename, "Walter", STRING_LENGTH ); strncpy( persons[2].Name, "Mueller", STRING_LENGTH ); strncpy( persons[2].Forename, "Maria", STRING_LENGTH ); strncpy( persons[3].Name, "Schmidt", STRING_LENGTH ); strncpy( persons[3].Forename, "Johanna", STRING_LENGTH ); for (int i = 0; i < 4; ++i) printf( "%d --- %s, %s\n", i, persons[i].Name, persons[i].Forename ); printf("\n"); // Nach Vornamen sortieren und ausgeben QuickSort_Forename(persons, 0, 3); for (int i = 0; i < 4; ++i) printf( "%d --- %s, %s\n", i, persons[i].Name, persons[i].Forename ); printf("\n"); // Nach Nachnamen sortieren und ausgeben QuickSort_Name(persons, 0, 3); for (int i = 0; i < 4; ++i) printf( "%d --- %s, %s\n", i, persons[i].Name, persons[i].Forename ); printf("\n"); // positiven Statuscode zurückgeben return 0; } \\ Bei Ausführung gibt das Programm folgendes aus: 0 - Mueller, Heinrich 1 - Schulze, Walter 2 - Mueller, Maria 3 - Schmidt, Johanna 0 - Mueller, Heinrich 1 - Schmidt, Johanna 2 - Mueller, Maria 3 - Schulze, Walter 0 - Mueller, Maria 1 - Mueller, Heinrich 2 - Schmidt, Johanna 3 - Schulze, Walter \\ Wie man sieht werden Heinrich und Maria, die den gleichen Nachnamen haben, beim ersten Sortieren (Vorname) in die richtige Reihenfolge gebracht. Allerdings geht diese Reihenfolge beim zweiten Sortiervorgang (Nachname) verloren. Mit einem Sortieralgorithmus à la [[c:bubblesort|BubbleSort]] oder [[c:selectionsort|SelectionSort]] hat man dieses Problem nicht. ===== Beispieldurchlauf ====== Da der QuickSort-Algorithmus erfahrungsgemäß nicht immer auf Anhieb zu verstehen ist folgt hier ein Beispieldurchlauf. Auch hier wird noch einmal das Problem Instabilität gezeigt. Dazu werden die beiden äußerlich identischen Elemente "66" jeweils mit einer Zahl versehen, die auf das Sortieren an sich allerdings keinen Einfluss hat. Die fiktive Liste | 27 | 66.1 | 89 | 35 | 32 | 50 | 73 | 66.2 | 14 | \\ \\ Pivotelement suchen | 27 | 66.1 | 89 | 35 ^ 32 | 50 | 73 | 66.2 | 14 | \\ Zu tauschendes Paar suchen | 27 | 66.1 | 89 | 35 ^ 32 | 50 | 73 | 66.2 | 14 | | i=0 | | | | | | | | j=8 | | | i=1 | | | | | | | j=8 | \\ Tauschen und Zählindizes weiterzählen | 27 | 14 | 89 | 35 ^ 32 | 50 | 73 | 66.2 | 66.1 | | | | i=2 | | | | | j=7 | | \\ Fortsetzen bis sich die Zählindizes "getroffen" haben | 27 | 14 | 89 | 35 ^ 32 | 50 | 73 | 66.2 | 66.1 | | | | i=2 | | | | j=6 | | | | | | i=2 | | | j=5 | | | | | | | i=2 | | j=4 | | | | | | 27 | 14 ^ 32 | 35 | 89 | 50 | 73 | 66.2 | 66.1 | | | | | i=j=3 | | | | | | | | | j=2 | i=3 | | | | | | \\ Mit Teilliste 1 fortfahren (Elemente 0 bis 2) | 27 ^ 14 | 32 | | i=0 | | j=2 | | i=0 | j=1 | | ^ 14 | 27 | 32 | | j=0 | i=1 | | \\ Teilliste 1.1 enthält nur Element 0 \\ Mit Teilliste 1.2 fortfahren (Elemente 1 und 2) ^ 27 | 32 | | i=1 | j=2 | | i=j=1 | | | j=0 | i=2 | \\ Teilliste 1.2.1 enthält nur Element 1 Teilliste 1.2.2 enthält nur Element 2 \\ Mit Teilliste 2 fortfahren (Elemente 3 bis 8) | 35 | 89 ^ 50 | 73 | 66.2 | 66.1 | | i=3 | | | | | j=8 | | | i=4 | | | j=7 | | | | i=4 | | j=6 | | | | | i=4 | j=5 | | | | | 35 ^ 50 | 89 | 73 | 66.2 | 66.1 | | | j=4 | i=5 | | | | \\ Mit Teilliste 2.1 fortfahren (Elemente 3 und 4) ^ 35 | 50 | | i=3 | j=4 | | i=j=3 | | | j=2 | i=4 | \\ Teilliste 2.1.1 enthält nur Element 3 Teilliste 2.1.2 enthält nur Element 4 \\ Mit Teilliste 2.2 fortfahren (Elemente 5 bis 8) | 89 ^ 73 | 66.2 | 66.1 | | i=5 | | | j=8 | | 66.1 ^ 73 | 66.2 | 89 | | | i=6 | j=7 | | | 66.1 | 66.2 ^ 73 | 89 | | | j=6 | i=7 | | \\ Mit Teilliste 2.2.1 fortfahren (Elemente 5 und 6) ^ 66.1 | 66.2 | | i=5 | j=6 | | 66.2 ^ 66.1 | | j=5 | i=6 | \\ Teilliste 2.2.1.1 enthält nur Element 5 Teilliste 2.2.1.2 enthält nur Element 6 \\ Mit Teilliste 2.2.2 fortfahren (Elemente 7 und 8) ^ 73 | 89 | | i=7 | j=8 | | i=j=7 | | | j=6 | i=8 | \\ Teilliste 2.2.2.1 enthält nur Element 7 Teilliste 2.2.2.2 enthält nur Element 8 \\ Zusammensetzen aller Teillisten bzw. Einzelelemente | 14 | 27 | 32 | 35 | 50 | 66.2 | 66.1 | 73 | 89 | \\ \\ \\ FIXME Mit dem Layout bin ich total unzufrieden. ===== Links ===== [[http://www.cs.oswego.edu/~mohammad/classes/csc241/samples/sort/Sort2-E.html|Animation]] ---- [[http://forum.proggen.org/viewtopic.php?f=39&t=1231|Autorendiskussion]]