Thomas Kramer

IT-COW | All posts tagged 'Quicksort'

Sortieren eines Zufallszahlen-Arrays mittels Quicksort in VBS

By Administrator at Februar 01, 2011 15:02
Filed Under: Algorithmen, Programmierung allgemein, Studium, VBScript

Um für die benötigte Laufzeitmessung eine bestimmte Größe festzulegen, stellte sich das Füllen eines Arrays mit Zufallszahlen als praktikabler gegenüber der vorherigen Variante heraus.

 

Nachfolgend meine Implementierung, wieder in VBScript. Das Syntax-Highlighting von blogengine.net funktioniert hier leider nicht korrekt.

 

Quellcode:

 

' Option Explicit bedeutet das die Variablen angegeben werden müssen
' Variablentypen müssen bei VBScript nicht angegeben werden

Option Explicit
' allgemein: _ bedeutet, das die darauffolgende Zeile zur vorangegangenen gehört
Dim fso, File, WFile, WLogFile, sText
Dim FILENAME, WRITE_FILENAME, LOG_FILENAME
Dim i, t, x
Dim Rekursions_Durchlaeufe, Vergleichs_Durchlaeufe, zeit_start, zeit_ende, zeit_aufwand
Dim Feldgroesse
const Zufallszahl_Untergrenze = 0
const Zufallszahl_Obergrenze  = 65535
' Durchlaeufe zuerst auf 0 setzen
Rekursions_Durchlaeufe=0
Vergleichs_Durchlaeufe=0

' ein dynamisches Array wird mit ReDim statt mit Dim angelegt
ReDim a(1)
Feldgroesse = Inputbox("Bitte geben Sie die Feldgröße n an", "Festlegen der Arraygröße")
ReDim a(Feldgroesse)
generiere_zufallszahlen

' Startzeit für Sortierung nehmen
zeit_start   = time
' Startzeit ausgeben (erstmal auskommentiert)
' x=msgbox("Startzeit für Sortierung, Fenster bitte sofort wegklicken. " & zeit_start,vbOkOnly,"Sortierungsstart")

Quicksort 0,ubound(a)

' Endzeit für Sortierung nehmen
zeit_ende    = time
' Differenz berechnen, das ist dann die aufgewandte Zeit für die Sortierung
zeit_aufwand = zeit_ende-zeit_start
' Zeitaufwand in hh:mm:ss umrechnen, mit FormatDateTime
' ---> mögliche Variablenwerte bei vBS siehe hier:
' http://www.asphelper.de/referenz/vbscript/formatdatetime.asp
zeit_aufwand = FormatDateTime(zeit_aufwand, vbLongTime)
 
' Ergebnis der Laufzeitanalyse ausgeben - mögliche Schaltflächen für msgbox siehe hier:
' http://www.vbarchiv.net/commands/MsgBox.php
' ("Laufzeitmessung" ist der Titel der Box, der zusammengesetzte String dagegen das, was in der
'   Box angezeigt wird. Der zweite Parameter gibt die Anzahl der angezeigten Schaltflächen an,
'   in x wird die betätigte Schaltfläche als Integerwert zurückgegeben)
x=MsgBox("Rekursions-Durchläufe: " & Rekursions_Durchlaeufe & ", Vergleichs-Durchläufe: " & Vergleichs_Durchlaeufe & _
         ", Endzeit: " & zeit_ende & _
         ", benötigte Zeit für Sortierung: " & zeit_aufwand, _
         vbOkOnly, _
         "Laufzeitmessung")

' --------------------- Generieren und Füllen des Arrays mit Zufallszahlen ------------------------         
sub generiere_zufallszahlen
  Dim iMin, iMax, i, iZahl

  iMin = 1
  iMax = 10

  For i = 0 To ubound(a)
    Randomize
    iZahl = Int((Zufallszahl_Obergrenze - Zufallszahl_Untergrenze + 1) * Rnd + Zufallszahl_Untergrenze)
    a(i)=iZahl
  Next
end sub

' -------------------------------- Quicksort-Algorithmus -----------------------------------------
' Der Quicksort wird hartkodiert auf das Array A angewandt
sub QuickSort(anfang, ende)
   dim links, rechts, pivot, h
   ' Grenzen festlegen
   links = anfang
   rechts = ende
   ' Pivot-Element rechts festlegen
   pivot=a(ende)
   do

       ' finde im Array von unten nach oben das erste Element das nicht in die Ordnung passt, also größer als das
       ' Pivot-Element ist - und erhöhe bis dahin den Zeiger "links" um 1
       while a(links)<pivot
         links=links+1
       wend
       ' finde im Array von oben nach unten das erste Element das nicht in die Ordnung passt, also kleiner als das
       ' Pivot-Element ist - und verringere bis dahin den Zeiger "rechts" um 1
       while pivot<a(rechts)
         rechts=rechts-1
       wend

       ' solange sich Untergrenzen-Zeiger und Obergrenzen-Zeiger nicht kreuzen...
       if links <= rechts then
          ' ... Elemente vertauschen an den gefundenen Positionen
          h = a(links)
          a(links) = a(rechts)
          a(rechts) = h
          ' dadurch...
          ' automatisch untere Grenze erhöhen,
          ' automatisch obere Grenze verringern
          links=links+1
          rechts=rechts-1
       end if
     Vergleichs_Durchlaeufe=Vergleichs_Durchlaeufe+1      
   ' Schleife fortfahren wie der Zeiger für die zu untersuchende Untergrenze tatsächlich kleiner
   ' als die Obergrenze ist       
   loop until links > rechts

   ' Beginn Rekursion  
   ' von Indexpositionen "anfang" (ursprünglicher Wert) bis "rechts" (errechneter Wert des letztkleineren Elements
   '  (im Vergleich zum Pivotelement)) Bereich des Arrays neu sortieren
   if anfang < rechts then
     ' Anzahl Rekursiondurchläufe berechnen
     Rekursions_Durchlaeufe=Rekursions_Durchlaeufe+1
     QuickSort anfang, rechts
   end if

   ' von Indexpositionen links (errechneter Wert des erstgrößeren Elements im Vergleich zum Pivotelement) bis ende
   ' (ursprünglicher Wert) Bereich des Arrays neu sortieren
   if links < ende then
     ' Anzahl Rekursiondurchläufe berechnen  
     Rekursions_Durchlaeufe=Rekursions_Durchlaeufe+1
     QuickSort links, ende
   end if
end sub

 

Anbei auch das Laufzeitmessungsdokument:

 

Laufzeitmessung.pdf (41,47 kb)

 

Monats-Liste