Pivotelement: Beim Sortieren mittels Quicksort bezeichnet das Pivotelement das Element, welches als Aufteilungsgrenze gewählt wird. Quicksort sortiert (rekursiv) alle Elemente "links" und "rechts" vom Pivotelement. Optimal ist dabei das Median-Element, welches zwei gleich große Teillisten erzeugt. Quelle: http://de.wikipedia.org/wiki/Pivotelement Es gilt aber auch: Im Best Case (bester Fall) wird das Pivotelement stets so gewählt, dass die beiden entstehenden Teillisten etwa gleich groß sind. In diesem Fall gilt für die asymptotische Laufzeit des Algorithmus O(n log n). Diese Zeitkomplexität gilt ebenso für den Average Case (durchschnittlichen Fall). Quelle: http://de.wikipedia.org/wiki/Quicksort => Es geht also darum, das Pivot-Element so zu wählen, dass der Worst-Case nicht auftritt, also O(n^2). Ein möglicher Ansatz ist es, immer das erste, das letzte oder das mittlere Element der Liste zu wählen. Dieser naive Ansatz ist aber relativ ineffizient. Eine andere Möglichkeit ist es den Median dieser drei Elemente zu bestimmen und als Pivotelement zu verwenden => Clever-Quicksort! (1. Variante) Ein anderer Ansatz ist, als Pivotelement ein zufälliges Element auszuwählen. Bei diesem randomisierten Quicksort ist die Wahrscheinlichkeit, dass das Pivotelement in jedem Teilungsschritt so gewählt wird, dass sich die Worst-Case-Laufzeit ergibt, extrem gering. Man kann davon ausgehen, dass er praktisch nie auftritt. => Clever-Quicksort! (2. Variante) Quelle: http://de.wikipedia.org/wiki/Quicksort