|
|
 |
|
 |
|
 |
 |
|
Hilfe zum Thema: Excel
 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 = 0
End Sub
Code eingefügt mit Syntaxhighlighter 3.0
|
Google-Anzeigen
|
|
 |
Geschickt von rlx, Do 01.05.2008 2:05
|
 |
 |
|
