Sinn von std::partial_sort()
-
Hallo,
habe von der Funktion
std::partial_sort()gelesen, und mir erschließt sich nicht der Sinn von dieser Funktion.
Warum kann ich den Bereich [first,middle) nicht einfach perstd::sort()sortieren?
-
Du sortierst bis zu einer gewissen Grenze, beziehst aber die Werte des gesamten Containers mit ein. Bei
std::sorthättest Du auch nur die Werte vonbeginbismiddle.
-
daersc schrieb:
Hallo,
habe von der Funktion
std::partial_sort()gelesen, und mir erschließt sich nicht der Sinn von dieser Funktion.
Warum kann ich den Bereich [first,middle) nicht einfach perstd::sort()sortieren?Spped. Wenn Du die kleinsten 40 Elemente eines Arrays mit 10 Mio Elementen brauchst, warum das gesamte Array sortieren??? parial_sort zieht die kleinsten 40 Elemente aus der großen Masse und plaziert sie vorne hin.
Partial_sort rearranges the elements in the range [first, last) so that they are partially in ascending order. Specifically, it places the smallest middle - first elements, sorted in ascending order, into the range [first, middle).
-
wenn du den Beeich [first,middle) einfach so sortierst ist nicht garantiert, dass *(middle-1) <= *it für alle it in [middle,last)
Beispiel (grausamer pseudocode...):
40231, middle = &3
sort first-middle ergibt 024 31
partial_sort ergibt 012 43
-
Man kann sogar noch weniger sortieren: std::nth_element
Das wäre zB praktisch, wenn die kleinsten 40 Elemente aus volkards Beispiel nicht sortiert sein müssen, oder einfach um den Median zu bestimmen.
Gruß,
SP