Dieses Verfahren scheint recht unbekannt zu sein, ich habe es nur auf www.sortieralgorithmen.de gefunden!
"Oet" steht für odd, even, transpose (dt. ungerade, gerade, versetzt), da das Verfahren auf dem zeitlich versetzten Vergleich von (geraden und ungeraden) Nachbarelementen beruht.
Innerhalb der äußeren Schleife (Zähler d) gibt es (in der ursprüngliche Version) zwei innere Schleifen und in jeder davon wird das Array vollständig durchlaufen. Da der Code der beiden inneren Schleifen im Grunde derselbe war, habe ich etwas rationalisiert: In meiner Version ist die innere Schleife (Zähler x) nur einmal vorhanden, die zusätzliche umhüllende Schleife (Zähler y) sorgt aber dafür, dass sie zweimal nacheinander aufgerufen wird.
Im ersten Durchgang werden alle Elemente ungerader Position mit ihrem rechten Nachbarn verglichen (also 1 mit 2, 3 mit 4, 5 mit 6 usw.) und ggf. miteinander vertauscht. Im zweiten Durchgang passiert dasselbe mit den Elementen ungerader Position (verglichen und ggf. vertauscht werden also 2 mit 3, 4 mit 5, 6 mit 7 usw.). Dadurch bewegt sich ein Element innerhalb eines äußeren Durchlaufs höchstens um 2 Positionen weiter, so dass sich sowohl die kleinen als auch die großen Elemente nur ganz allmählich in Richtung ihres endgültigen Platzes bewegen, was man auch sehr schön in der Visualisierung sieht.
OetSort ist gewissermaßen die Umkehrung von BiDiBubblesort. Dort werden ja in jedem Durchlauf das kleinste und das größte Element nach ganz vorn bzw. nach ganz hinten durchgereicht, so dass sich das Array von den Rändern her zur Mitte hin sortiert, während bei OetSort sich durch das langsame "Einschweben" die sortierten Elemente von der Mitte her auf die Ränder zubewegen.
Die äußere Schleife wird n/2 mal wiederholt, spätestens dann ist das gesamte Array sortiert. Von der Laufzeit her bringt OetSort keine Vorteile gegenüber Bubblesort, aber allein wegen der einmaligen Effekte bei der Visualisierung habe ich es in meine Sammlung aufgenommen. ;-) Ihr solltet auf jeden Fall auch mal die Anordnungen "Absteigend", "Quadrat", "Kreuz", "Doppelkreuz" und "Streifen" ausprobieren!
Sub OetSort(aDaten())
Dim x As Long, y As Long, d As Long, varTemp
For d = 1 To UBound(aDaten) / 2
For y = 1 To 2
For x = y To UBound(aDaten) - 1 Step 2
If aDaten(x) > aDaten(x + 1) Then
varTemp = aDaten(x + 1)
aDaten(x + 1) = aDaten(x)
aDaten(x) = varTemp
End If
Next
Next
Next
End Sub
Code eingefügt mit Syntaxhighlighter 3.0
|
