InPlaceAlgorithmen

InPlaceAlgorithmen bezeichnen Algorithmen, die die Eingabedaten größtenteils ohne zusätzlichen Speicher außerhalb der Eingabe verarbeiten. Typischerweise wird nur konstanter Zusatzspeicher verwendet, also O(1) neben dem Eingang. In manchen Beschreibungen wird zusätzlich der rekursive Stapel berücksichtigt, sodass dort O(log n) Zusatzspeicher zulässig ist. Strengere Definitionen verlangen jedoch wirklich konstanten zusätzlichen Platz unabhängig von der Eingangsgröße.

Charakteristisch ist, dass das Ergebnis direkt im ursprünglichen Datenbereich entsteht, ohne umfangreiche Kopien oder externe Datenstrukturen. Dadurch sinkt der Speicherbedarf erheblich, was besonders in speicherlimitierten Umgebungen von Vorteil ist. Bezüglich der Stabilität und Laufzeit variiert die Situation stark: In-Place-Algorithmen können langsamer oder komplexer implementiert werden; viele klassische In-Place-Sortierverfahren sind nicht stabil (zum Beispiel Quicksort oder Heapsort), während andere stabile Varianten existieren, oft auf Kosten der Komplexität.

Typische Beispiele umfassen Sortieralgorithmen wie Quicksort mit in-place-Partitionierung, Heapsort, Selectionsort und Insertionsort. Auch Transformations- und Manipulationsaufgaben wie das In-Place-Rotieren einer Matrix oder das Entfernen von Duplikaten in einem Array ohne neue Speicherstrukturen fallen in diese Kategorie. In der Praxis finden In-Place-Algorithmen breite Anwendung in eingebetteten Systemen, großen Datenstrukturen und situationsabhängig dort, wo Speicher begrenzt ist.

Der Begriff ist in der Informatik verbreitet, wobei die genaue Definition hinsichtlich des zusätzlichen Speichers je nach Quelle variieren kann. Grundsätzlich beschreiben InPlaceAlgorithmen jedoch Ansätze, die Eingaben direkt nutzen und modifizieren, um Ressourcen zu sparen.