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

Quellcode

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

Aktuelle Seite Back To Top
Druckansicht | Feedback | Favoriten
Copyright © Visual Basic World, 2000-2022 | Kontakt | Impressum