In-Place und Out-of-Place Sortierverfahren!

[Busse_D]

Moin!

Ich muss eine Facharbeit zum Thema "Sortieralgorithmen" erarbeiten.

Natürlich möchte ich mich dabei auch auf In-place und Out-of-Place Sortierverfahren beziehen. Die grundsätzlichen Unterschiede habe ich bereits erkannt. Im Verlauf der Facharbeit vergleiche ich "Bubblesort" und "Quicksort", beides In-Place Sortierverfahren. Am Anfang der Facharbeit werde ich den Unterschied zwischen In-Place und Out-of-Place erläutern, aber mir fehlt noch ein schlagendes Argument, weswegen ich mich im folgenden nur noch auf In-place beziehe.

Spielt da die Verbesserung der PC-Hardware oder ähnliches eine Rolle? Also praktisch die "veraltung" von Out-of-Place. Richtig spitze wäre auch ein Zitat von einem bewährten Informatiker à la "Out-of-Sort wird heute seltener benutzt, da....", worauf ich auch meine Begründung beziehen kann!

Ich sage schon mal Vielen Dank,

Dominik

[VaNaTiC]

Hmm, kenne kein Zitat.

Im Prinzip ist Out-Place einfach höherer Speicherbedarf, dafür Orginaldaten unberührt. Das wird halt seltener genutzt, ist aber meiner Meinung weder veraltet noch ein Grund darauf nicht näher einzugehen

[Busse_D]

Danke für die schnelle Antwort!

Also mit nicht näher auf Out-of-Place eingehen, meinte ich ja nur dass wir eben nur 2 In-Place Sortieralgorithmen vergleichen.

Lehrer meinte wäre gut und okay, aber wir sollten begründen weswegen wir nur auf In-Place eingehen. Weiterhin meinte er dann eben dass dafür relativ schnell ein schlagendes Argument, besten Falls ein Zitat zu finden sei.

Also Hardware spielt doch da schon eine Rolle? Kann man nicht vielleicht so etwas sagen wie, (überspitzt dargestellt) riesige NASA-Mengen gehen eher in Richtung Out-of-Place wenn man sortiert und so kleine Sortierungen (1 3 5 2 4 in richtige Reihenfolge bringen) eher für den "Hausgebrauch". Eben ziemlich überspitzt dargestellt, aber vllt kann ja einer fort führen wo ich drauf hinaus will! :confused:

Vielen Dank nochmal für die Schnell Antwort und für zukünftige!

[VaNaTiC]

Der Grund ist der normale Nutzungsfall:

Man will i.d.R. einfach nur die Daten sortieren. Dabei spielt dann die unsortierte Orginalmenge keine Rolle. Daraus folgt ich benötige diese nicht im Speicher, also tue ich das auch nicht.

Ausnahme ist wie gesagt nur, wenn ich das Orginal behalten muss.

Denn der Mehrspeicherverbrauch kann extreme Folgen bei größeren Datenmengen haben, d.h. gerade auch auf "kleinen" Systemen ist man froh, wenn die Daten in den Speicher passen, da will man keine doppelten Daten unnützerweise im Speicher.

Im Prinzip ist das der Hauptgrund, denn In-Place-Sortierungen tauschen nach unterschiedlichen Verfahren einzelne Elemente aus, was bedeutet, dass ich einen Speicherverbrauch = Liste + 1 Element habe, was sich sehr gut skalieren lässt.

Außerdem kostet das Allozieren/Freigeben zusätzlichen Speichers natürlich auch Zeit. Das ist zwar beim Sortieren das geringere Übel, aber u.U. eben nicht vernachlässigbar.

[Busse_D]

So jetzt nochmal vielen Dank! :-)

Das hat mich auf jeden Fall schon etwas weitergebracht.

Also bei den In-Place Verfahren meinst du "Liste + Element" wegen diesem Pavot Element, anhand dessen die Elemente sortiert werden, ja?

Und bei Out-Of-Place Verfahren bleibt der Originalzustand der Daten immer gespeichert und frisst deswegen zusätzlich Speicher? Bei In-Place wird es einfach sortiert, und das ist ja meist auch dass was man will?

Hast du vielleicht ein Beispiel wo man es wollen würde, die Originalsortierung beizubehalten? Ich begründe immer alles gern anhand von Beispielen! :-P

Vielen Dank!