title image


Smiley CombSort - Wir "durchkämmen" das Array
CombSort ist ein sogenannter umhüllender Algorithmus; der eigentliche Sortieralgorithmus ist Bubblesort. Der Name ist abgeleitet von Kamm (engl. Comb), denn CombSort "durchkämmt" das Array mehrfach, wobei immer feinere Kämme zum Einsatz kommen. Dabei werden ähnlich wie bei ShellSort erst weit auseinanderliegende Elemente verglichen und ggf. vertauscht, mit jedem Durchgang wird dann der "Gap" (die "Lücke") verkleinert, so dass irgendwann die unmittelbar nebeneinander liegenden Elemente verglichen werden. Wenn dieser Zustand erreicht ist, ist CombSort identisch mit BubbleSort. Als ersten Gap wählt man typischerweise die Anzahl der Elemente durch 1,3. Mit jedem äußeren Durchlauf wird dann der Gap erneut durch 1,3 geteilt, so dass irgendwann 1 erreicht wird. Sobald der Gap 1 ist, könnte man die innere Schleife am Ende immer um eins verkürzen, da spätestens jetzt der jeweils größte Wert entweder gerade dorthin verschoben wurde oder bereits dort stand. In der Praxis bringt das aber nur wenig. Da die Elemente in der Regel schon gut vorsortiert sind, lohnt sich aber auf jeden Fall der Einsatz einer Prüfvariable (bei mir c). Diese wird mit jedem Tausch um eins hochgezählt. Bleibt sie innerhalb eines inneren Durchlaufs auf 0 hat kein Tausch stattgefunden; folglich ist das Array sortiert.CombSort ist ShellSort wirklich sehr ähnlich (das sieht man auch in der Visualisierung) und es erreicht trotz des internen BubbleSort-Algorithmus auch fast gleich gute Laufzeiten.      Sub CombSort(aDaten())    Dim x As Long, varTemp, schritt As Long, c As Long    schritt = UBound(aDaten)    Do        c = 0        If schritt > 1 Then schritt = Int(schritt / 1.3)        For x = 1 To UBound(aDaten) - schritt            If aDaten(x) > aDaten(x + schritt) Then                varTemp = aDaten(x + schritt)                aDaten(x + schritt) = aDaten(x)                aDaten(x) = varTemp                c = c + 1            End If        Next    Loop Until schritt = 1 And c = 0End Sub Code eingefügt mit Syntaxhighlighter 3.0


mfg

Ralf

Der Computer löst Probleme, 
die es ohne ihn nicht gäbe!



geschrieben von

Anhang
Bild 45334 zu Artikel 1913275

Login

E-Mail:
  

Passwort:
  

Beitrag anfügen

Symbol:
 
 
 
 
 
 
 
 
 
 
 
 
 

Überschrift: