Zyklische Partitionierung: Ein bis zu 1,5-mal schnelleres Partitionierungs-Algorithmus

Sequenzpartitionierung ist ein grundlegender Algorithmus in der Computerprogrammierung, der Zahlen in einer Sequenz basierend auf einem Pivot-Wert umordnet. Das Ziel ist es, alle Zahlen kleiner als den Pivot-Wert zuerst zu platzieren, gefolgt von den restlichen Zahlen. Es gibt verschiedene Anwendungen der Partitionierung, einschließlich QuickSort und der Ermittlung des Medianwerts einer Sequenz. Derzeit gibt es zwei bekannte Partitionierungs-Algorithmen: das Lomuto-Schema und das Hoare-Schema. Das Hoare-Schema wird oft in der Praxis bevorzugt, da es weniger Umstellungen innerhalb des Arrays durchführt. Ein neues Partitionierungsschema namens "zyklische Partition" wird vorgeschlagen, das dem Hoare-Schema ähnelt, aber 1,5-mal weniger Umstellungen durchführt. Das zyklische Partitionierungsschema gilt als fast optimal, da die Anzahl der Wertzuweisungen fast gleich der Anzahl der Werte ist, die ursprünglich nicht an ihrem Platz sind. Das Hoare-Schema wird überprüft und seine Zeitkomplexität beträgt O(N), unabhängig davon, wo sich die beiden Scans treffen. Das Hoare-Schema erfordert 3L/2 Zuweisungen, wobei L die Anzahl der Werte ist, die nicht an ihrem Platz sind. Das Konzept der Zuweisungszylinder wird eingeführt, das für die Optimierung des Hoare-Partitionierungsschemas erforderlich ist. Verschiedene Fälle von Umstellungen werden vorgestellt, einschließlich zyklischer Linksverschiebung und Umkehrung einer Sequenz, um zu zeigen, dass einige Umstellungen mehr Zuweisungen erfordern als andere.