Dreieckstausch

Grundidee und Standardverfahren

Der Dreieckstausch ist ein Verfahren der Programmierung, mit dem die Werte zweier Variablen ausgetauscht werden. Er ist beispielsweise in Sortieralgorithmen wie Bubblesort ein typischer Anwendungsfall. Die Bezeichnung bezieht sich auf die drei Zuweisungen, die beim klassischen Verfahren ausgeführt werden.

Eine Hilfsvariable speichert zunächst den Wert, der sonst beim Überschreiben verloren ginge. Für die Variablen v₁ und v₂ sowie die temporäre Hilfsvariable t lautet das allgemeine Prinzip:

t := v₁ v₁ := v₂ v₂ := t

Dabei wird t im Programmcode häufig temp genannt. Nach den drei Schritten enthält v₁ den ursprünglichen Wert von v₂, während v₂ den ursprünglichen Wert von v₁ enthält.

Tausch von Zahlenwerten ohne Hilfsvariable

Zahlenwerte beziehungsweise Ordinale können auch ohne Hilfsvariable durch wiederholtes Addieren und Subtrahieren vertauscht werden. Eine mögliche Folge lautet:

v₁ := v₁ + v₂ v₂ := v₁ − v₂ v₁ := v₁ − v₂

Eine zweite Variante ist:

v₁ := v₁ − v₂ v₂ := v₁ + v₂ v₁ := v₂ − v₁

Diese Verfahren sollten nicht bei Gleitkommazahlen eingesetzt werden, weil es zu Auslöschungen kommen kann. Außerdem handelt es sich streng genommen nicht mehr um einen Dreieckstausch.

Für Zahlenwerte ist außerdem folgende Zuweisung möglich:

v₁ := v₂ + 0 · (v₂ := v₁)

Auch hierbei wird der Austausch in einer Anweisung ohne eine ausdrücklich verwendete Hilfsvariable ausgedrückt.

Tausch mit XOR-Verknüpfungen

Sind die Werte der beiden Variablen binär verknüpfbar, kann der Austausch durch drei XOR-Verknüpfungen ohne Hilfsvariable erfolgen. XOR ist eine binäre Verknüpfung; für sie gilt das Gesetz (a XOR b) XOR b = a. Die drei Zuweisungen sind:

v₁ := v₁ XOR v₂ v₂ := v₁ XOR v₂ v₁ := v₁ XOR v₂

Eine wichtige Voraussetzung ist, dass die beiden Variablen an verschiedenen Stellen im Speicher liegen. Liegen sie nicht an verschiedenen Speicherstellen, setzt dieses Verfahren den Wert der Variablen auf 0 zurück.

In einigen Programmiersprachen, unter anderem C++ und C#, funktioniert für Datentypen mit unterstützter binärer XOR-Verknüpfung auch die Anweisung:

v1 ^= v2 ^= v1 ^= v2;

Der Ausdruck a ^= b bedeutet dabei a := a XOR b.

Mehrfachzuweisungen und Prozessorbefehle

Einige Programmiersprachen unterstützen Mehrfachzuweisungen mithilfe von Tupeln. Dazu gehören Ruby, Python, F# und Powershell. Der Tausch kann dort direkt formuliert werden:

(v₁, v₂) := (v₂, v₁)

Dadurch wird der klassische Dreieckstausch mit einer Hilfsvariable unnötig. Moderne Prozessoren verfügen außerdem über eigene Befehle zum Vertauschen von Variablen. Im Artikel werden dafür xchg und cmpxchg genannt.

Programmbeispiele

Die Beispiele zeigen verschiedene Umsetzungen des Variablentauschs:

• Assembler für x86, x64 und ARM verwendet xchg v1, v2.
• In C# wird zunächst eine generische Swap-Funktion mit ref-Parametern und der Hilfsvariable temp gezeigt. Ein weiteres Beispiel verwendet Interlocked.Exchange; im Kommentar wird diese Methode als bevorzugt bezeichnet und darauf hingewiesen, dass sie zu einer einzelnen Instruktion kompiliert.
• F# vertauscht die Werte mit let swap (v1, v2) = (v2, v1).
• Powershell verwendet $v1,$v2 = $v2,$v1.
• JavaScript nutzt beim Austausch benachbarter Feldelemente die Hilfsvariable temp: Der Wert von feld[i] wird gespeichert, feld[i] erhält feld[i+1], und anschließend erhält feld[i+1] den gespeicherten Wert.
• Python verwendet die Mehrfachzuweisung x, y = y, x.

Damit stellt der Artikel den klassischen Austausch mit Hilfsvariable, arithmetische und binäre Verfahren ohne Hilfsvariable sowie sprachspezifische Kurzformen gegenüber.