InplacePartitionierung

InplacePartitionierung bezeichnet das in-situ Aufteilen einer Datenfolge, typischerweise eines Arrays, in zwei oder mehr Teilmengen, ohne nennenswerten zusätzlichen Speicher zu verwenden. Das bedeutet, alle Operationen erfolgen durch Vertauschen oder Verschieben der vorhandenen Elemente im ursprünglichen Speicher.

Typische Anwendung ist die Partitionierung im Rahmen von Sortier- und Selektionsalgorithmen. Die häufigsten Partitionierungsschemata sind die Lomuto-Partitionierung und die Hoare-Partitionierung. Bei der Lomuto-Variante wird ein Pivot-Element gewählt, und zusammen mit einem Laufindex werden Elemente, die kleiner oder gleich dem Pivotwert sind, an die Vorderseite verschoben. Die Hoare-Partitionierung arbeitet mit zwei Indizes, die sich entgegenlaufen, und tauscht Elemente, sodass alle kleineren Elemente vor dem Pivot landen, ohne das Pivot zwingend an seine endgültige Position zu setzen.

Drei-Wege-Partitionierung (Dutch National Flag) wird eingesetzt, wenn viele Duplikate auftreten, um die Partitionierung effizienter zu gestalten.

Eigenschaften: Inplace-Partitionierung ist in der Regel instabil; die relative Reihenfolge gleicher Elemente kann verloren gehen. Die Zeitkomplexität ist im Mittel O(n); im schlimmsten Fall kann sie O(n^2) erreichen, insbesondere bei ungünstiger Pivotwahl. Der Vorteil ist der geringe Speicherbedarf, der Nachteil mögliche erhöhte Schreiboperationen und Abhängigkeit von Pivot-Strategie.

Anwendungen: QuickSort nutzt Inplace-Partitionierung im Durchschnitt; Quickselect verwendet Partitionierung, um das k-te Kleinste zu finden, ohne die gesamte Folge zu sortieren.

Varianten: Mehrere Pivots, um bessere Lastverteilung zu erzielen; stabilität erfordert oft zusätzlichen Speicher oder andere Techniken, bleibt aber meist außerhalb des rein in-place-Ansatzes.