Dreieckstausch

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

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

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 sollte 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

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}

Die beiden Variablen müssen dazu allerdings an verschiedenen Stellen im Speicher liegen. Ist das nicht der Fall, setzt dieser Dreieckstausch den Wert der Variablen auf 0 zurück.

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

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

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)
{
    // preferred 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

JavaScript

var temp = feld[i];
feld[i] = feld[i+1];
feld[i+1] = temp;

Python

x, y = y, x

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.