Dreieckstausch

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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.

Das allgemeine Prinzip sieht wie folgt aus:

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

Dreieckstausch von Zahlenwerten

[Bearbeiten | Quelltext bearbeiten]

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

oder:

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:

Dreieckstausch mit Binärwerten

[Bearbeiten | Quelltext 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 , auch gänzlich ohne Hilfsvariable verwirklichen.

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 .

Mehrfachzuweisungen

[Bearbeiten | Quelltext 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:

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

Programmbeispiele

[Bearbeiten | Quelltext 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)
{
    // 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