Auf den Bucketsort bin ich durch Zufall gestoßen, als ich Assembler programmiert habe, und war durch seine Schnelligkeit sofort überzeugt. Also machte ich mich auf die Suche Bucketsort in VB via der Hilfe des Internets zu integrieren. Leider fand ich keinen Sourcecode. Also schrieb ich ihn selber und hier ist er.
Hinweis, der Bucketsort ist zwar der schnellste Algorithmus den ich je gesehen habe, jedoch benötigt er viel Speicherplatz beim sortieren:
hier ein kleines Beispiel:
Menge der zu sortierenden Zahlen (max. größe 200000 Integer) 20.000.000. Der Bucketsort benötigte lediglich 1,036Sekunden (bei 100.000.000 gerademal 10Sekunden) wobei der Quicksort Algorithmus 31Sekunden brauchte. Jedoch braucht der Bucketsort etwa 80MB Speicher, der Quicksort brauchte bei mir im Test ebenfalls 80MB. (Testmaschine: Turion64 Dual Core TL-60, 1GB RAM)
Public Function BucketSort(ByVal Buckets As Integer, ByVal z() As Integer) As String 'Iterativ
'Für das Array z() muss gelten 0<=z(i)<=Bucktes
'Buckets sind die benötigten "Eimer" - in dem Falle Auslagerungen, die Anzahl der Buckets muss also
'laut Definition um sinnvoll zu arbeiten größer oder gleich der größten Zahl sein.
'Sinnvoller Einsatz: sortieren von Telefonnummern, PLZ, BLZ, Kontonummern
'Start der Zeitmessung
Dim start As DateTime
Dim ende As DateTime
start = DateTime.Now
'Histogramm erstellen
Dim n As Integer = z.Length - 1
Dim k(Buckets) As Integer
Dim a As Integer
For a = 0 To Buckets - 1 'alles auf 0 setzen
k(a) = 0
Next a
For a = 0 To n - 1
k(z(a)) = k(z(a)) + 1
Next a
'sortieren
Dim x As Integer = 0
For a = 0 To Buckets - 1
While k(a) > 0
z(x) = a
x = x + 1
k(a) = k(a) - 1
End While
Next a
'Ende der Zeitmessung
ende = DateTime.Now
'umrechnen in MilliSekunden und zurückgeben
BucketSort = (ende.Hour * 60 * 60 * 1000) + (ende.Minute * 60 * 1000) + (ende.Second * 1000) + ende.Millisecond
BucketSort = BucketSort - ((start.Hour * 60 * 60 * 1000) + (start.Minute * 60 * 1000) + (start.Second * 1000) + start.Millisecond)
End Function
2 Kommentare zum Snippet