1.) Einem Pivotelement,
2.) einer Teilliste von Elemente, die kleiner oder gleich dem Pivotelement sind,
3.) sowie einer Liste von Elementen, die größer als das Pivotelement sind.
Zur Herstellung der Sortierung wird die Liste der Elemente von vorne her nach Elementen
durchsucht, die größer als das Pivotelement sind. Diese werden dann mit Elementen vertauscht,
die kleiner als das Pivotelement sind, wobei diese ab dem Listenende gesucht werden.
Ist keine Vertauschung mehr möglich, wird das Pivotelement sortiert eingefügt
und die beiden Teilfolgen werden separat nach Quicksort sortiert.
Anzahl der Schritte die zum Sortieren nötig sind:
- O(n*log(n))
- im ungüstigem Fall: O(n²)
Idee:
Man könnte Quicksort so verfeinern, dass, wenn nur noch wenige Elemente zu sortieren
sind, man Bubblesort laufen lässt, das in einem solchen Fall viel schneller arbeitet.