Reihenfolgeerhaltung

Reihenfolgeerhaltung bezeichnet in Mathematik und Informatik die Eigenschaft einer Abbildung, die Ordnung zwischen Elementen zu bewahren. Genauer gilt: Eine Abbildung f von einer geordneten Menge M in eine geordnete Menge N ist ordnungs-erhaltend, wenn für alle a, b in M gilt, dass a ≤ b impliziert f(a) ≤ f(b). In der strikten Version folgt aus a < b auch f(a) < f(b). Solche Abbildungen werden oft als monotone oder monoton wachsende Funktionen bezeichnet. In Teilordnungen spricht man von einer order-preserving Abbildung; bijektive Abbildungen, deren Umkehrung ebenfalls ordnungserhaltend ist, heißen Ordnungsisomorphismen.

Im Kontext der Sortierung ist Reihenfolgeerhaltung eng mit Stabilität verknüpft. Eine stabile Sortierung bewahrt die relative Reihenfolge gleichwertiger Elemente; das heißt, wenn zwei Objekte denselben Schlüssel haben, bleibt ihre ursprüngliche Reihenfolge nach der Sortierung erhalten. Stabilität ist eine gewünschte Eigenschaft vieler Sortieralgorithmen und beeinflusst das Verhalten in mehrstufigen Sortierprozessen.

Beispiele: Die Funktion f(x) = x^3 ist auf den reellen Zahlen strikt monoton wachsend und erhält daher die Reihenfolge. Die Funktion f(x) = -x ist strikt monoton fallend und erhält die Ordnung nicht, sondern kehrt sie um. Auf bestimmten Teilmengen oder mit anderen Ordnungen können auch andere Abbildungen reihenfolgeerhaltend sein.

Anwendungen finden sich in der Analysis, der Diskreten Mathematik, der Datenverarbeitung und beim Entwurf von Algorithmen, insbesondere wenn Transformationsregeln die sortierten oder geordneten Beziehungen zwischen Objekten wahren müssen.