Sprache: VB
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 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
Alte URL:
/snippet/bucketsort-algorithmus-fuer-vb2005/275
Also ich habe mir mal diese Algorithmus angeguckt und war erstaunt auf welche einfache Art man ein Zahlenfeld sortieren kann. Allerdings hat dein Algo hier einen Fehler und zwar musst du die „-1“ bei „Dim n As Integer = z.Length – 1“ entfernen da die erste kleinste Zahl sonst nicht berücksichtigt wird!
Im Allgemeinen ist der Algorithmus gut, nur deine Version ist sehr schlecht umgesetzt. Angefangen bei der Zeitnahme, das kann man mit einer Stopwatch Klasse viel besser lösen. Dann kommt das setzen auf 0 des „Eimer“ Felds, das ist nicht nötig da alle Eimer schon eine 0 haben. Dann kommt noch ein Fataler fehler, du übergibst das Array „z()“ als Kopie, du solltest es aber als Referenz übergeben ansonsten musst du das Array wieder als Kopie zurückgeben was äußerst ineffizient ist! Der Rest ist vollkommen in Ordnung.
Hi, z.length-1 ist in der Tat ein Fehler, der aber durch den Umstand, das man ein zum Beispiel Array(10) as Integer erzeugt (weil man denkt 10 Zahlen!!! aber in Wirklichkeit eine Array von Index 0 bis 10 erstellt wird = 11 Felder) nicht aufgefallen ist. Die Zeitnahme ist eigentlich nur Magulatur, ob ich nun Stopwatch oder die beschriebene Version nehme macht in der asymptotischen Laufzeit (Landau Notation) keinen unterschied und war im übrigen nur zum testen und staunen gedacht. Zum Thema Kopie übergeben, theoretisch ist das ja richtig – aber in der Praxis funktioniert auch der ByVal „Schalter“ und ich muss keine Zurückkopierung machen! Ob nun beim definieren eines Arrays (Dim k(Buckets) as…) sich das Array auf Null befindet entzog sich meines Wissens. In anderen Programmiersprachen ist das nicht gang und geben, also zu Sicherheit noch mal Nullen.