http://de.wikipedia.org/wiki/Quicksort
da steht bei Laufzeit:
Zitat:
Ein Ansatz, um worst-case-Laufzeiten zu verhindern, ist, als Pivotelement ein zufällig bestimmtes Element zu wä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, so dass man praktisch von einer Komplexität von O(n·log(n)) ausgehen kann. Eine andere Möglichkeit ist die Verwendung des Medians von z.B. drei zufällig gewählten Elementen. Durch geschickte Wahl des Pivotelementes kann man aber nur das mittlere schlechteste Verhalten verbessern. Vollständig verhindern kann man das Eintreten des Worst Cases jedoch nicht.
Über google solltest du vom prinzip bis zu vollständigen Implementierungen alles finden
Lukas Erlacher
Suche Grafiktablett. Spenden/Gebrauchtangebote willkommen.
Gotteskrieger gesucht!
For it is the chief characteristic of the religion of science that it works. - Isaac Asimov, Foundation I, Buch 1