Implementierung: Partition Hoare/Lomuto-light

Implementiere eine einfache Lomuto-Partition um das letzte Element als Pivot.

Wer Partition schreibt, versteht Quicksort-Bugs und Off-by-one an den Grenzen. Nützlich beim Lesen von JDK- und Lehrcode.

Vertiefung

Eine Lomuto-light-Variante kann das letzte Element als Pivot wählen. Vor dem Scan liegen links der Grenze nur Werte, die der gewählten Relation entsprechen; zwischen Grenze und Scan liegen bereits untersuchte Werte der anderen Gruppe. Nach dem Scan wird das Pivot an die Grenze gesetzt.

Eine Hoare-nahe Variante lässt zwei Indizes laufen und tauscht Paare, die auf der falschen Seite stehen. Sie benötigt oft weniger Tausche, doch ihr Rückgabewert definiert eine Bereichsgrenze. Beide Varianten sind korrekt, wenn Invarianten, Vergleichsoperatoren und Rekursionsintervalle zusammenpassen.

Schwierigkeitsstufen

1. Eine Lomuto-Invariante während jedes Scanschritts prüfen.
2. Hoare-Zeiger bei Duplikaten sicher fortschreiten lassen.
3. Zu jedem Schema korrekte rekursive Teilintervalle angeben.

Fallstricke

Gemischte Regeln sind gefährlich, etwa ein Hoare-Rückgabewert mit Lomuto-Grenzen. Bei gleichen Pivotwerten müssen Zeiger trotzdem Fortschritt machen, damit die Schleife terminiert.