- 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. 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.
Wikimedia Foundation.
