Dreieckstausch

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Als Dreieckstausch bezeichnet man in der Programmierung ein Verfahren zum Austausch der Werte zweier Variablen. Dabei wird eine Hilfsvariable verwendet, um den Wert der Variablen, die zuerst überschrieben wird, zwischenzuspeichern. Ein typischer Anwendungsfall des Dreieckstauschs besteht zum Beispiel in einigen Sortieralgorithmen wie dem Bubblesort.

Funktionsweise[Bearbeiten]

Das allgemeine Prinzip sieht wie folgt aus:

t := v_1
v_1 := v_2
v_2 := t

Hierbei ist t die temporäre Hilfsvariable, in Programmcode meist als temp bezeichnet, und v_1 und v_2 sind die zu vertauschenden Variablen.

Dreieckstausch von Zahlenwerten[Bearbeiten]

Zwei weitere Möglichkeiten zum Tauschen von Ordinalen ohne Hilfsvariablen besteht im wiederholten Addieren und Subtrahieren:

v_1 := v_1 + v_2
v_2 := v_1 - v_2
v_1 := v_1 - v_2

oder:

v_1 := v_1 - v_2
v_2 := v_1 + v_2
v_1 := v_2 - v_1

Diese Methode kann nicht bei Gleitkommazahlen eingesetzt werden, da es zu Auslöschungen kommen kann. Streng genommen handelt es sich nicht mehr um einen Dreieckstausch.

Für Zahlenwerte funktioniert außerdem:

v_1 := v_2 + 0 \cdot (v_2 := v_1)

Dreieckstausch mit Binärwerten[Bearbeiten]

Wenn es sich bei den Werten der beiden auszutauschenden Variablen um binär verknüpfbare Werte handelt, kann man den Tausch durch wiederholte XOR-Verknüpfungen, basierend auf dem Gesetz (a\,\underline{\lor}\,b)\,\underline{\lor}\,b = a, auch gänzlich ohne Hilfsvariable verwirklichen.

v_1 := v_1\,\underline{\lor}\,v_2
v_2 := v_1\,\underline{\lor}\,v_2
v_1 := v_1\,\underline{\lor}\,v_2

In einigen Programmiersprachen, unter anderem C++ und C#, funktioniert auf Datentypen welche die binäre XOR-Verknüpfung unterstützen, die Anweisung

v1 ^= v2 ^= v1 ^= v2;

Hierbei steht der Ausdruck a ^= b für a := a\,\underline{\lor}\,b.

Mehrfachzuweisungen[Bearbeiten]

Manche Programmiersprachen, wie zum Beispiel Ruby, Python, F# und Powershell, unterstützen auch Mehrfachzuweisungen mit Hilfe von Tupeln, wodurch ein Dreieckstausch unnötig wird:

(v_1, v_2) := (v_2, v_1)

Moderne Prozessoren besitzen zudem eigene Befehle für den Vertausch von Variablen, dazu gehören xchg und cmpxchg.

Programmbeispiele[Bearbeiten]

Assembler
# x86, x64, ARM
xchg v1, v2
C#
void Swap<T>(ref T v1, ref T v2)
{
    var temp = v1;
    v1 = v2;
    v2 = temp;
}
void Swap<T>(ref T v1, ref T v2)
{
    // prefered method 
    // compiles to single instruction
    v2 = Interlocked.Exchange(ref v1, v2); 
}
Tuple<T, T> Swap<T>(Tuple<T, T> tuple)
{
    return new Tuple(tuple.Item1, tuple.Item2);
}
F#
let swap (v1, v2) = (v2, v1)
Powershell
$v1,$v2 = $v2,$v1