Visual Basic World - Programmierung und BeispieleVisual Basic World - Tipps und TutorialsVisual Basic World - Source-Code und Forum

<leer>

Tipp 037: Sortier-Algorithmen: BubbleSort, SelectionSort und ShellSort im Vergleich

Autor: Benjamin Wilger, Alexander Kopatz  VB-Version: Visual Basic 6.0   Download: Beispielprojekt Tipp-037

Beschreibung

In Zeiten stetig steigenden CPU-Performance und immer leistungsfähiger Systeme mag sich der ein oder andere fragen, ob die Geschwindigkeits-Optimierung der eigenen Software noch sinnhaftig ist. Die einfache Antwort auf diese Frage lautet: Selbstverständlich. Entscheidend für die Ausführgeschwindigkeit der eigenen Anwendung ist jedoch oft nicht allein ein sauber geschriebener Code oder ein besonders schneller Prozessor sondern der richtige Algorithmus. Visual Basic bietet zur Implementierung eigener Sortierfunktionen unzählige Möglichkeiten und Varianten. Drei bewährte und zum Teil sehr schnelle Verfahren wollen wir Ihnen hier vorstellen. Hierbei vergleicht dieser Tipp unmittelbar die verschiedenen Möglichkeiten zur Sortierung mittels Bubblesort, Selectionsort und Shellsort.

Bubblesort

Der Klassiker unter den Sortier-Algorithmen ist Bubblesort. Obgleich nicht atemberaubend schnell arbeitet  Bubblesort doch nach einem einfachen Prinzip. Dabei werden die zu sortierenden Elemente einer Folge in einem Index von unten nach oben durchlaufen. Bei einem Durchlauf werden stets die beiden übereinander liegenden Elemente miteinander verglichen. Der jeweils größere Wert wird, sofern er sich noch nicht auf der höheren Stelle des Index befindet, nach oben verschoben bzw. getauscht. Sodann wird dieser Wert ebenfalls mit dem darauffolgenden Element der Liste vergliche und sortiert und so fort. Ein Vorteil dieses Algorithmus besteht darin, dass keine zweite Liste zur Sortierung benötigt wird, sondern alle Elemente an Ort und Stelle sortiert werden können (in-place). Die zu sortierenden Elemente und hierbei insbesondere die großen Zahlen steigen dabei quasi wie Blasen nach oben in der Liste auf.

Selectionsort

Dieses Verfahren lässt sich ebenfalls "in-place" Realisieren, es wird also lediglich eine Liste bzw. ein Index benötigt. Obgleich eine Implementierung mit Selectionsort nicht zwangsläufig einer Sortierung mittels Bubblesort überlegen sein muss liefert das Verfahren in der Programmier-Praxis jedoch meist deutlich bessere Ergebnisse. Das Selectionsort-Verfahren basiert dabei quasi auf der Trennung der zu sortierenden Liste in zwei Bereiche. Einen bereits sortierten Bereich und einen noch nicht sortierten Bereich. Der erste Durchlauf sucht daher in der Vorhandenen Menge den Kleinsten Wert und vertauscht diesen mit der ersten Position. Diese Position ist damit sortiert und aus den unsortierten Werten (ab Position zwei) kann der nächste Minimumwert ermittelt werden. Dieser wird sodann (falls abweichend) mit Position zwei getauscht. Eine neue Runde beginnend bei Position drei des Index nimmt ihren Lauf und so fort.

Shellsort

Der Shellsort-Algorithmus, von Donald Shell entwickelt, arbeitet im Vergleich zu den beiden vorgenannten Algorithmen deutlich effizienter. Die vorgenannten Verfahren verlieren einen erheblichen Teil ihrer Leistung durch den Umstand, dass einzelne Elemente vielfach und über "größere" Strecken hin und her kopiert werden müssen. Beim Shellsort-Verfahren indes werden die einzelnen Elemente einer Liste zunächst virtuell in kleiner Untergruppen unterteilt. Diese werden sodann für sich sortiert. Anschließend werden diese Untergruppen wieder zu größeren Gruppen formiert und sortiert und so fort, bis schließlich die Gesamtmenge sortiert vorliegt. Zu beachten ist hierbei, dass die jeweiligen Schrittlänge der Untergruppen einen erheblichen Einfluss auf die Geschwindigkeit der Sortierung haben kann.

Zusatzinformationen

» Wikipedia-Artikel: Bubblesort-Algorithmus
» Wikipedia-Artikel: Selectionsort-Algorithmus
» Wikipedia-Artikel: Shellsort-Algorithmus
» Wikipedia-Artikel: Übersicht verschiedener Sortierverfahren

Quellcode

frmSortAlgos
CommandButton            Command1
Form                     frmSortAlgos
ListBox                  List1
ListBox                  List2
' VISUAL BASIC WORLD
' ===========================================
' Das große Portal zum Thema Visual Basic.
'
' Wenn Ihnen dieser Source Code gefallen hat,
' dann empfehlen Sie Visual Basic World bitte
' weiter und/oder setzen Sie einen Link auf:
'
' http://www.visualbasicworld.de/
'
' Vernetzen Sie sich mit uns:
'
' http://twitter.com/visualbasicwrld
'
' Autor: Benjamin Wilger [Algorithmen nach MSDN]

Option Explicit
Sub Command1_Click() Dim lMyArray(0 To 1500) As Long Dim vTemp1 As Variant Dim vTemp2 As Variant Dim vTemp3 As Variant Dim iLoop As Integer Dim t As Double Me.Cls List1.Clear List2.Clear List3.Clear Randomize Timer For iLoop = LBound(lMyArray) To UBound(lMyArray) lMyArray(iLoop) = Int(Rnd * 1500) + 1 Next iLoop vTemp1 = lMyArray vTemp2 = lMyArray vTemp3 = lMyArray t = Timer Call BubbleSortNumbers(vTemp1) Me.Print " BubbleSort: " & Format(Timer - t, "0.000s") For iLoop = LBound(vTemp1) To UBound(vTemp1) List1.AddItem vTemp1(iLoop) Next iLoop t = Timer Call SelectionSortNumbers(vTemp2) Me.Print " SelectionSort: " & Format(Timer - t, "0.000s") For iLoop = LBound(vTemp2) To UBound(vTemp2) List2.AddItem vTemp2(iLoop) Next iLoop t = Timer Call ShellSortNumbers(vTemp3) Me.Print " ShellSort: " & Format(Timer - t, "0.000s") For iLoop = LBound(vTemp3) To UBound(vTemp3) List3.AddItem vTemp3(iLoop) Next iLoop End Sub
Sub BubbleSortNumbers(iArray As Variant) Dim lLoop1 As Long Dim lLoop2 As Long Dim lTemp As Long For lLoop1 = UBound(iArray) To LBound(iArray) Step -1 For lLoop2 = LBound(iArray) + 1 To lLoop1 If iArray(lLoop2 - 1) > iArray(lLoop2) Then lTemp = iArray(lLoop2 - 1) iArray(lLoop2 - 1) = iArray(lLoop2) iArray(lLoop2) = lTemp End If Next lLoop2 Next lLoop1 End Sub
Sub SelectionSortNumbers(vArray As Variant) Dim lLoop1 As Long Dim lLoop2 As Long Dim lMin As Long Dim lTemp As Long For lLoop1 = LBound(vArray) To UBound(vArray) - 1 lMin = lLoop1 For lLoop2 = lLoop1 + 1 To UBound(vArray) If vArray(lLoop2) < vArray(lMin) Then lMin = lLoop2 Next lLoop2 lTemp = vArray(lMin) vArray(lMin) = vArray(lLoop1) vArray(lLoop1) = lTemp Next lLoop1 End Sub
Sub ShellSortNumbers(vArray As Variant) Dim lLoop1 As Long Dim lHold As Long Dim lHValue As Long Dim lTemp As Long lHValue = LBound(vArray) Do lHValue = 3 * lHValue + 1 Loop Until lHValue > UBound(vArray) Do lHValue = lHValue / 3 For lLoop1 = lHValue + LBound(vArray) To UBound(vArray) lTemp = vArray(lLoop1) lHold = lLoop1 Do While vArray(lHold - lHValue) > lTemp vArray(lHold) = vArray(lHold - lHValue) lHold = lHold - lHValue If lHold < lHValue Then Exit Do Loop vArray(lHold) = lTemp Next lLoop1 Loop Until lHValue = LBound(vArray) End Sub

ANZEIGE <leer>
<leer> Aktuelle Seite Back To Top
Druckansicht | Feedback | Favoriten
Copyright © Visual Basic World, 2000-2014 | Kontakt | Impressum

Visual Basic World @ Twitter

Folgen Sie Visual Basic World!

Visual Basic World @ Twitter
Wenn Ihnen Visual Basic World gefällt, dann folgen Sie uns doch bei Twitter (@visualbasicwrld).
Vielen Dank!



Fragen & Forum

Wenn Sie offene Fragen zur Programmierung mit Visual Basic haben und in der Tipps & Tricks Sektion oder bei den Tutorials nicht fündig wurden, dann werfen Sie doch einen Blick ins Visual Basic World Forum.


Visual Basic World Forum

Im Forum erhalten Sie schnell Hilfe und finden eine Vielzahl an bereits beantworteten Fragen und Problemen.

Viel Vergnügen bei der Benutzung!


Visual Basic World Relaunch

Nach einiger Zeit der Iniaktivität erstrahlt visualbasicworld.de mit frischem Design in neuem Glanze.

Dabei hat sich nicht nur optisch einiges getan, auch technisch setzt das neue Web-Layout Maßstäbe.

Im Hintergrund arbeitet unser Team zudem an der Aktualisierung, Erweiterung und Ergänzung des gesamten bisherigen Contents.


Visual Basic World Relaunch

Wenn Sie Fragen oder Anregungen zum neuen Design haben, so freuen wir uns über Ihr Feedback!

Schauen Sie also in Kürze wieder rein und empfehlen Sie Visual Basic World weiter.


Fotografie & Design

Fotograf in Mannheim und Heidelberg.

Unterstützen Sie VB-World!

Wenn Ihnen Visual Basic World gefällt, dann unterstützen Sie uns!



Das geht am einfachsten, indem Sie einen Link auf visualbasicworld.de setzen oder senden Sie doch folgende QR-Grafik an Ihre Freunde:

Visual Basic World

Außerdem würden wir uns sehr freuen, wenn Sie uns bei Twitter (@visualbasicwrld) folgen.
Vielen Dank!