std::list::sort - Welcher Algorithmus?
-
Hallo,
weis jemand von euch zufällig, welchen algorithmus std::list::sort verwendet? Vermutlich quicksort.
Ich muss aber eine bereits fast sortierte Liste sortieren, und dafür ist quicksort ja ?O(n)?, auf jeden Fall ungeeignet, BubbleSort wäre hier z.B. besser.
Wo finde ich infos zu den von sort verwendeten Algorithmen und wie kann ich ggf. den Algorithmus einstellen?
Danke, Jochen
-
vermutlich introsort.
das ist fast so geil wie quicksort bei durcheinander-listen und kackt bei sortierten listen nicht ab. (das ist in wirklichkeit auch nur quicksort, aber mit einem wächter, der schaut, ob quicksort abkackt und dann schnell auf heapsort umschaltet).
-
Gast221212 schrieb:
Ich muss aber eine bereits fast sortierte Liste sortieren, und dafür ist quicksort ja ?O(n)?
Nicht O(n) sondern O(n^2).
Wo finde ich infos zu den von sort verwendeten Algorithmen
Z.B. in der Dokumentation deiner Standardbibliothek. Der Standard legt keine worst-case-complexity für std::list::sort fest sondern nur eine durchschnittliche Komplexität von O(n*logn). Einige Implementationen verwenden z.B. einen stabilen Merge-Sort-Algo mit worst-case-complexity von O(n*logn). Letztlich musst du aber in deine Doku bzw. in den Quellcode deiner Implementation schauen.