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. Das allgemeine Prinzip sieht wie folgt aus:

temp := v1
v1 := v2
v2 := temp

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 (unter Ausnutzung des Gesetzes (A xor B) xor B = A) auch gänzlich ohne Hilfsvariable verwirklichen:

v1 := v1 xor v2
v2 := v1 xor v2
v1 := v1 xor v2

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

v1 := v1 + v2
v2 := v1 - v2
v1 := v1 - v2

oder:

v1 := v1 - v2
v2 := v1 + v2
v1 := v2 - v1

Dies funktioniert nur bei ganzen Zahlen, weil es bei Gleitkommazahlen zu Auslöschungen kommen kann. Streng genommen handelt es sich nicht mehr um einen Dreieckstausch.


Nur in einigen Sprachen (unter anderem C++) und wenn der Datentyp die binäre XOR-Verknüpfung unterstützt, funktioniert die Anweisung

v1 ^= v2 ^= v1 ^= v2,

wobei

a ^= b

für

a := a XOR b

steht.

Für Zahlenwerte funktioniert außerdem:

v1 := v2 + 0 * (v2 := v1)

Manche Programmiersprachen, wie zum Beispiel Ruby oder Python, unterstützen auch Mehrfachzuweisungen, wodurch ein Dreieckstausch unnötig wird:

v1, v2 := v2, v1