Feedback

VB - Bucketsort Algorithmus für VB2005

Veröffentlicht von am 25.10.2006
(2 Bewertungen)
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)
GFU-Schulungen  [Anzeige]

ASP.NET Core und Angular Komplett für .NET-Entwickler

Sie  lernen in drei (3) Tagen wie man mit  ASP.NET Core und den Technologien  MVC, Entity Framework, WebAPI und  Razor professionelle sowie moderne  Web-Anwendungsarchitekturen aufbaut.  Die Schulung ist der perfekte  Einstieg um insbesondere datengetriebene  und präsentationsorientierte  Applikationen auf Basis der robusten und  skalierbaren ASP.NET Core  Plattform zu erstellen. Nach der Veranstaltung kennen Sie die Konzepte von Angular und können Angular in neue und bestehende ASP.NET-Anwendungen einsetzen.

Visual Studio Team Foundation Server 2017/2015 (TFS) für Administratoren - Kompakt

Nach dieser Schulung beherrschen Sie die Grundlagen des TFS. Sie erledigen administrative Aufgaben schnell und sicher.

    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
Abgelegt unter Bucketsort, Sortieren.

2 Kommentare zum Snippet

Tim Hartwig schrieb am 25.10.2006:
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.
Christian Storm schrieb am 26.10.2006:
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.
 

Logge dich ein, um hier zu kommentieren!