Selbstähnlichkeit
Ein häufiges, wenn nicht sogar das vorherrschende Strukturmerkmal nicht nur, vor allem aber hierarchischer bzw. hierarchisch strukturierter Systeme in sowohl lebender als auch nichtlebender Natur, Wissenschaft, Gesellschaft, Technik und sogar Mathematik (Fraktale, Algorithmen, Kettenbrüche und -wurzeln, rekursive Funktionen, Mehrfachintegrale) ist die Selbstähnlichkeit, die bedeutet, daß Sub-/Teilsysteme ähnlich wie das Gesamtsystem oder wenigstens das Hyper-/Meta(teil)system aufgebaut - strukturiert - sind, und, da Ähnlichkeit immer beidseitig ist, auch umgekehrt, die Meta-/Hyper-/Gesamtstruktur ähnelt jedem ihrer Teile. Das bedeutet zudem auch, daß die Sub-/Teilsysteme, konkret ihre Strukturen selbst einander ähneln. Diese hierarchieübergriefende Ähnlichkeit kann sich über mehrere, bei mathematischen Objekten sogar unendlich viele Hierarchieebenen (evtl. nur nach „unten“, sichtbar durch Vergrößerung (siehe z.B. die Mandelbrotmenge, das sog. „Apfelmännchen“) und ggf. sogar auch nach „oben“, sichtbar durch Verkleinerung, s. beide Animationen am Sierpinski-Dreieck) hinwegziehen.
Noch eindrucksvoller ist diese Unendlichkeit nach oben und nach unten m.E. bei diesen beiden „Flügen“ über den Sierpinski-Teppich sichtbar:
Erstmalig ausführlich beschrieben und mathematisch formuliert wurde diese autoreferentielle (=selbstbezügliche) System- bzw. konkret Struktureigenschaft vom Mathematker Benoît B. Mandelbrot.
Die Selbstähnlichkeit findet sich auch im Bereich der (nicht nur Sortier-)Algorithmen, doch dazu fand ich bislang in der Literatur nichts. Hierbei muß streng zwischen der Selbstähnlichkeit des Algorithmus' selbst, also der Deskription, des Abbildes, des Planes des (Sortier-)Prozesses, und der des eigentlichen (Sortier-)Prozesses, also des Ablaufens des Algorithmus', unterschieden werden.
Eine elegante Möglichkeit, die Selbstähnlichkeit der (Algorithmenablauf-)Prozesse algorithmisch und programmiertechnisch zu beschreiben bzw. abzubilden, womöglich sogar die einzig adäquate, sofern die Anzahl der Hierarchieebenen unbekannt ist, ist die sog. Rekursion. So enthalten z.B. die rekursiven Versionen der Sortieralgorithmen einen, zwei oder noch mehr (rekursive) Aufruf(e) ihrer selbst. Ja sogar jeder einfache Schleifendurchlauf läßt sich durch einen rekursiven Aufruf ersetzen. Wenn z.B. Quicksort sich im Algorithmus selbst zweimal aufruft, bedeutet das, daß während des Quicksorts der gesamten zu sortierenden Menge (oder eines übergeordneten Teilabschnittes) vollständige Quicksorts, wenn auch kleinerer, untergeordneter Bereiche, durchlaufen werden. Das setzt sich, wenn dieser Algorithmus eben auf der gesamten Sortiermenge abläuft, ggf. über mehrere Hierarchieebenen mit etlichen Aufrufen abwärts hinweg, sodaß zum Schluß nur noch einelementige Sortierbereiche, an denen es nichts mehr zu sortieren gibt, oder zweielementige, die mit einer einfachen Vergleichs- und ggf. Tauschoperation zu sortieren sind, übrigbleiben.
Die Eigenschaft „Selbstähnlichkeit“ des Algorithmus' färbt also auf den Prozeß seines Ablaufens ab und umgekehrt, beide bedingen einander.
Diese Selbstähnlichkeit des Algorithmus', genauer des Prozesses seines Ablaufens ist ggf. auch visuell bzw. dynamisch wahrnehmbar, sofern einem klar ist, daß man auf ähnliche Abläufe in verschiedenen Größenbereichen zu achten hat. Mehr noch: Diese Eigenschaft ist ggf. auch an der teilsortierten Menge, demnach statisch zu erkennen. Besonders gut ist das beim Circlesort der Fall. Am besten ist es, man startet mit einer unsortierten gleichverteilten Menge (voreingestellt) und läßt dann mit Circlesort die Startmenge mit nur einem Schleifendurchlauf vorsortieren. Die Struktur der daraufhin erhaltenen Menge ist gut erkennbar selbstähnlich: Jede Hälfte der vorsortierten Menge sieht etwa wie die auf die Hälfte verkleinerte Gesamtmenge aus, und umgekehrt sieht die Gesamtmenge wie eine auf da Doppelte vergrößerte halbe Menge aus. Weiterhin sehen die Viertel wie verkleinerte Hälften, die Hälften wie vergrößerte Viertel aus, usw., das zieht sich auch noch feiner in kleinere Bereiche hinein, s. Bild:
Man kann aber auch größere Interpretationssprünge machen: Jede Menge enhält vier Viertel oder acht Achtel usw. ihrer selbst und umgekehrt in Richtung Meta-/Hyper(teil)system/-struktur.
Nicht ganz so schön, aber immer noch gut zu erkennen ist die Selbstähnlichkeit auch an der teilsortierten Gesamtmenge beim Quicksort: Dort enthält die Gesamt- bzw. jede Teilmenge (außer der kleinsten) ein ähnliches, verkleinertes Abbild ihrer selbst, allerdings nur einmal: