Wann hat man beim Qicksort den worst case?
1 Antwort
Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer
programmieren
Im Worst Case (schlechtesten Fall) wird das Pivotelement stets so gewählt, dass es das größte oder das kleinste Element der Liste ist. Dies ist etwa der Fall, wenn als Pivotelement stets das Element am Ende der Liste gewählt wird und die zu sortierende Liste bereits sortiert vorliegt. Die zu untersuchende Liste wird dann in jedem Rekursionsschritt nur um eins kleiner und die Zeitkomplexität wird beschrieben durch O(n²).
