Code-Beispiel

Combsort Sortieralgorithmus

Lizenz:	Erster Autor:	Letzte Bearbeitung:
k. A.	Sebastian	26.03.2010

Beim Sortieralgorithmus Combsort handelt es sich um eine Abwandlung des bekannten und einfach zu implementierenden Bubblesort-Algorithmus. Combsort ist - vereinfacht dargestellt - im schlechtesten Fall genauso ineffektiv wie der einfache BubbleSort, erzielt jedoch je nach Eingabedatenmenge eine bessere Laufzeit als dieser.

Combsort ist ein nicht-stabiles Sortierverfahren. Das bedeutet, dass Elemente mit gleichem Sortierschlüssel nach dem Sortieren nicht mehr notwendigerweise in der gleichen Reihenfolge vorliegen.
Sortiert man etwa die folgende Tabelle aufsteigend nach dem Preis mit einem nicht-stabilen Sortierverfahren,

119  Teurer Joystick

299  Spielekonsole

299  Fahrrad

149  Flachbildschirm

kann folgendes Ergebnis entstehen:

119  Teurer Joystick

149  Flachbildschirm

299  Fahrrad

299  Spielekonsole

Des Weiteren sortiert Combsort In-Place, d.h. es wird lediglich eine konstante, von der Größe der Eingabe unabhängige Menge zusätzlichen Speichers beim Sortieren in Anspruch genommen. Der Algorithmus arbeitet also auf dem Eingabefeld und muss kein zweites Array vorhalten.

Wer sich für die Idee hinter dem Algorithmus interessiert, wird im Wikipedia-Artikel zu Combsort fündig. Der folgende Algorithmus enthält zudem eine Modifikation, siehe Combsort11.

' Demonstration des Combsort-Sortieralgorithmus

' Lizenz: Public Domain oder äquivalent

' Quelle: http://www.freebasic.net/forum/viewtopic.php?t=15289

' Zuerst veroeffentlicht: W. Dobosiewicz,

'                   An efficient variation of bubble sort,

'                   Information Processing letters 11(1):5-6, 1980



Declare Sub combsort(a() As Integer)



Cls



Print "SORTIEREN MIT COMBSORT"

Print



'Zu sortierendes Array vom Typ Integer: a

'Feld mit 1 Million Elementen anlegen

Redim As Integer a(1 To 1000000)



'Variablen fuer Zeitmessung

Dim As Double st, et



'Zaehlvariable fuer FOR-Schleife

Dim As Integer count



'Pseudozufallszahlengenerator initialisieren

Randomize Timer



'Array a mit Zufallszahlen fuellen

Print "  => Erzeuge Zufallszahlen."

Print

For count = Lbound(a) To Ubound(a)

    a(count) = Rnd * 1000

Next



Print "  => Beginne Sortiervorgang."



'Startzeit festhalten

st = Timer



'Feld mit Combsort sortieren

combsort(a())



'Schlusszeit festhalten

et = Timer



'Den folgenden Code-Block entkommentieren, um sortierte Zahlen angezeigt zu bekommen.

'Achtung: Im Beispiel sind es 1.000.000 Zahlen!



'For count = LBound(a) To UBound(a)

'        Print a(count),

'Next



'Anzahl der sortierten Elemente und verstrichene Zeit anzeigen

Print

Print Using "  => ##,###,### Elemente zu sortieren dauerte ###.###### Sekunden."; (Ubound(a)-LBound(a)+1), CDBL(et-st)

Print

Print

Print "Beliebige Taste zum Beenden druecken."

Sleep

End







Sub combsort(a() As Integer)

    Dim As Integer i, gap, swaps, first, last

    first = Lbound(a)

    last = Ubound (a)

    gap = last - first + 1

    Do

        gap = Int(gap / 1.3)

        If gap < 1 Then

            gap = 1

        End if

        If gap = 9 Or gap = 10 Then

            gap = 11

        End if

        i = first

        swaps = 0

        Do

            If a(i) > a(i+gap) Then

                Swap a(i), a(i+gap) 'Vertauschen!

                swaps = 1

            End If

            i += 1

        Loop Until (i + gap) > last

    Loop Until (gap = 1) And (swaps = 0)

End Sub 'combsort

Zusätzliche Informationen und Funktionen

Das Code-Beispiel wurde am 26.03.2010 von Sebastian angelegt.
Die aktuellste Version wurde am 26.03.2010 von Sebastian gespeichert.

Bearbeiten

Versionen

Impressum • Nutzungsbedingungen • Datenschutz

Microsoft, Windows, Windows NT, XBOX und Visual Basic sind entweder eingetragene Marken oder Marken der Microsoft Corporation in den USA und/oder anderen Ländern. Weitere auf dieser Homepage aufgeführten Produkt- und Firmennamen können geschützte Marken ihrer jeweiligen Inhaber sein.