Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
In-situ, ex-situ bei rekursiven Aufrufen
Hallo,
auf den Übungsfolien steht, dass der QuickSort ein ex-situ/out-of-place Sortierverfahren ist. Verständlich, da der Algorithmus rekursiv implementiert einen Aufrufstapel erzeugt.
Auf den Vorlesungsfolien ist der QuickSort in pseudo-code eigentlich auch rekursiv dargestellt, aber auf einmal in-situ.
Übersehe ich dort was?
Ich meine auch gelesen zu haben, dass man den rekursiven Aufrufstapel auch bei der Speicherbetrachtung auch vernachlässigen kann,
wenn dem aber so wäre, wüsste ich ebenfalls nicht, wie ich das in der Klausur handhaben soll? (Insbesondere, wenn gefragt wird, ob der quicksort ein in-situ/ex-situ sortierverfahren ist?)
in-situ und ex-situ hat nichts mit Rekursion zu tun, sondern damit, wohin die Ergebnisse gespeichert werden. Genauer: wenn die Eingabe unverändert bleibt und eine Ausgabe mit dem Ergebnis (hier eine neues, sortiertes Array) erfolgt, dann ist das ex-situ. Falls das Ergebnis direkt in die Eingabe gespeichert wird (hier also in das Eingabearray), dann ist das in-situ.
Stimmt, das steht tatsächlich so auf den Vorlesungsfolien und das hatte ich auch nicht gesehen und erklärt auch woher die abweichenden Angaben kommen…
Auf den Vorlesungsfolien steht es tatsächlich so mit dem array,
auf den Übungsfolien ist es allgemeiner formuliert, so dass um ex-situ zu erfüllen, der Speicherverbrauch abh. von der Eingabegröße ist. (Tf. 11, Folie 50)
Zusätzlich:
“Rekursive Algorithmen, deren Aufruftiefe von der Eingabegröße abhängt, arbeiten ge-
naugenommen out-of-place, denn für die Funktionsschachteln auf dem Aufrufestapel
wird Speicherplatz benötigt. Manchmal bezeichnet man aber auch solche Algorithmen
mit einem Speicherverbrauch von O( log ( n )) als in-place”