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.
|
|
Wer ist online?
Buchempfehlung
FreeBASIC-Chat
FreeBASIC-Nachrichten jetzt auch über Twitter erhalten. Follow us!
Bearbeiten
Versionen