Tipp-Upload: VB.NET 0256: Nicht vergleichsbasiertes Sortieren mit Bucketsort

Hinweis zum Tippvorschlag  

Dieser Vorschlag wurde noch nicht auf Sinn und Inhalt überprüft und die Zip-Datei wurde noch nicht auf schädlichen Inhalt hin untersucht.
Bitte haben Sie ein wenig Geduld, bis die Freigabe erfolgt.

Über den Tipp  

Dieser Tippvorschlag ist noch unbewertet.

Der Vorschlag ist in den folgenden Kategorien zu finden:

• Algorithmen
• Mathematik

Dem Tippvorschlag wurden folgende Schlüsselwörter zugeordnet:
bucketsort, sortieren, O(n), lineare Laufzeit, nicht vergleichsbasiert, eimer

Der Vorschlag wurde erstellt am: 16.04.2008 16:40.
Die letzte Aktualisierung erfolgte am 16.04.2008 16:40.

Zurück zur Übersicht

Beschreibung  

Mit nicht vergleichsbasierten Sortieralgorithmen wie dem hier vorgestellten Bucketsort können Werte in linearer Laufzeit, anstatt wie bei anderen Verfahren z.B. mit quadratischer, sortiert werden. Vorraussetzung dafür ist, dass der Wertebereich, in dem die Suchschlüssel liegen, bekannt ist.

Die Werte werden hier in ein Array aus "Eimern" direkt einsortiert und dann nacheinander ausgelesen. Aus einem Wert muss daher der Index des Eimers ersichtlich sein bzw. aus einer Funktion entstehen.

Die Funktionen sind generisch implementiert und erwarten die Werte, Zahl der Eimer und eine Transformationsfunktion bzw. einen Typen, der von einer entsprechenden Schnittstelle abgeleitet ist.

Es werden einmal Zahlen aus einem festen Wertebereich und Städte nach Bundesländern sortiert. Zu einem ähnlichen Beispiel siehe [link url="http://de.wikipedia.org/wiki/Bucketsort"]Wikipedia[link]

Schwierigkeitsgrad

Verwendete API-Aufrufe:

Download: Download des Beispielprojektes [8,63 KB]

' Dieser Source stammt von http://www.activevb.de
' und kann frei verwendet werden. Für eventuelle Schäden
' wird nicht gehaftet.

' Um Fehler oder Fragen zu klären, nutzen Sie bitte unser Forum.
' Ansonsten viel Spaß und Erfolg mit diesem Source!
'
' Beachten Sie, das vom Designer generierter Code hier ausgeblendet wird.
' In den Zip-Dateien ist er jedoch zu finden.

' ----------- Anfang Projektgruppe Bucketsort.sln  -----------
' ---------- Anfang Projektdatei Bucketsort.vbproj  ----------
' ----------------- Anfang Datei Module1.vb  -----------------

Module Sorting

    Interface IBucketSortable

        Function Transformation() As Integer

    End Interface

    Public Sub Bucketsort(Of T)(ByVal Values As T(), ByVal NumBuckets As Integer, ByVal Func _
        As Func(Of T, Integer))

        Dim Length As Integer = Values.Length - 1

        Dim Buckets(NumBuckets) As List(Of T)

        ' Transformieren und die Eimer zuweisen
        For Each Item In Values

            Dim idx As Integer = Func(Item) ' Index

            If Buckets(idx) Is Nothing Then Buckets(idx) = New List(Of T)
            Buckets(idx).Add(Item)
        Next

        ' Aus den Eimern lesen
        Dim Index As Integer = 0

        For i = 0 To NumBuckets

            If Buckets(i) Is Nothing Then Continue For

            ' Solange etwas in das Array schreiben, bis der aktuelle Eimer leer ist
            While Buckets(i).Count > 0
                Values(Index) = Buckets(i)(Buckets(i).Count - 1)
                Index += 1
                Buckets(i).RemoveAt(Buckets(i).Count - 1) ' Löschen

            End While

        Next

    End Sub

    ' Wenn wir ein IBucketSortable haben, muss die Transformation nicht angegeben werden
    Public Sub Bucketsort(Of T As IBucketSortable)(ByVal Values As T(), ByVal NumBuckets As Integer)

        Bucketsort(Values, NumBuckets, Function(x As IBucketSortable) x.Transformation)

    End Sub

End Module

Module Module1

    Class Stadt

        Implements IBucketSortable

        Public Name, Bundesland As String

        Public Function Transformation() As Integer Implements _
            Sorting.IBucketSortable.Transformation

            Static Bundesländer As String() = {"Baden-Württemberg", "Bayern", "Berlin", _
                "Brandenburg", "Bremen", "Hamburg", "Hessen", "Mecklenburg-Vorpommern", _
                "Niedersachsen", "Nordrhein-Westfalen", "Rheinland-Pfalz", "Saarland", _
                "Sachsen", "Sachsen-Anhalt", "Schleswig-Holstein", "Thüringen"}

            Return Array.IndexOf(Bundesländer, Bundesland)

        End Function

        Public Overrides Function ToString() As String

            Return String.Format("{0} ({1})", Name, Bundesland)

        End Function

    End Class

    Sub Main()

        Dim Werte As Integer() = {-14, 5, 14, 6, 3, 13, 3, 12, 0, 6, 2, 1}

        Console.WriteLine("Vor dem Sortieren")
        Array.ForEach(Werte, AddressOf Console.WriteLine)

        Sorting.Bucketsort(Werte, 30, Function(x) x + 14)

        Console.WriteLine("Nach dem Sortieren")
        Array.ForEach(Werte, AddressOf Console.WriteLine)

        Dim Städte As Stadt() = {New Stadt() With {.Name = "Dresden", .Bundesland = _
            "Sachsen"}, New Stadt() With {.Name = "Flensburg", .Bundesland = _
            "Schleswig-Holstein"}, New Stadt() With {.Name = "Pullach", .Bundesland = _
            "Bayern"}, New Stadt() With {.Name = "Dresden", .Bundesland = "Sachsen"}, New _
            Stadt() With {.Name = "Rostock", .Bundesland = "Mecklenburg-Vorpommern"}, New _
            Stadt() With {.Name = "München", .Bundesland = "Bayern"}, New Stadt() With {.Name _
            = "Leipzig", .Bundesland = "Sachsen"}, New Stadt() With {.Name = "Passau", _
            .Bundesland = "Bayern"}}

        Console.WriteLine()
        Console.WriteLine()

        Console.WriteLine("Städte nach Bundesländern sortiert")

        Sorting.Bucketsort(Städte, 16 - 1)
        Array.ForEach(Städte, AddressOf Console.WriteLine)

        Console.ReadKey()

    End Sub

End Module

' ------------------ Ende Datei Module1.vb  ------------------
' ----------- Ende Projektdatei Bucketsort.vbproj  -----------
' ------------ Ende Projektgruppe Bucketsort.sln  ------------

	

Diskussion  

Diese Funktion ermöglicht es, Fragen, die die Veröffentlichung des Tipps betreffen, zu klären, oder Anregungen und Verbesserungsvorschläge einzubringen. Nach der Veröffentlichung des Tipps werden diese Beiträge nicht weiter verlinkt. Allgemeine Fragen zum Inhalt sollten daher hier nicht geklärt werden.

Um eine Diskussion eröffnen zu können, müssen sie angemeldet sein.