VB.NET-Tipp 0151: Laufende Daten sortieren mit TreeSort
von Dario
Beschreibung
Oft steht man vor dem Problem, eine Ansammlung von Daten sortieren zu müssen. Hat man die Gesamtheit der Daten beispielsweise in einer Liste oder einem Array bereits vorliegen, so kann man diese mit .NET-Bordmitteln sehr schnell sortieren. Interessanter wird das Problem, wenn man die einzelnen Werte nicht auf einmal, sondern schrittweise erhält. Natürlich könnte man die Werte in einer Liste sammeln und einfach am Ende sortieren. Effizienter wäre es aber, die Zeit zwischen den einzelnen Eingängen zu nutzen und die neuen Elemente gleich an ihren richtigen Platz zu schieben. Gewöhnliche Listen sind dafür kaum geeignet, das Einfügen in der Mitte kann langsam sein.
Statt dessen kann ein Binärbäum verwendet werden. Ein solcher Baum besteht aus einer Wurzel und je zwei Teilbäumen (einem linken und einem rechten). Beim Einfügen eines neuen Wertes gilt es nur zu beachten, dass in linken Teilbaum nur Werte stehen, die kleiner sind als die Wurzel, im rechten Teilbaum dagegen alle, die größer oder gleich der Wurzel sind. Wenn wir jedes neue Element direkt in den Baum einfügen, brauchen wir am Ende den Baum nur in der Reihenfolge linker Teilbaum - Wurzel - rechter Teilbaum durchlaufen um die sortierte Ausgabe zu erhalten.
Schwierigkeitsgrad: | Framework-Version(en): .NET Framework 3.0, .NET Framework 3.5, .NET Framework 4 | .NET-Version(en): Visual Basic 2008, Visual Basic 2010 | Download: |
' Dieser Quellcode 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! ' Projektversion: Visual Studio 2008 ' Option Strict: An ' Option Explicit: An ' Option Infer: Aus ' ' Referenzen: ' - System ' - System.Data ' - System.Deployment ' - System.Xml ' - System.Core ' - System.Xml.Linq ' - System.Data.DataSetExtensions ' ' Imports: ' - Microsoft.VisualBasic ' - System ' - System.Collections ' - System.Collections.Generic ' - System.Data ' - System.Diagnostics ' - System.Linq ' - System.Xml.Linq ' ' ############################################################################## ' ################################ Module1.vb ################################## ' ############################################################################## Imports System.Linq.Enumerable Imports System.Collections.Generic Module TreeSort ' Basisklasse für einen Binärbaum Public MustInherit Class BinaryTree(Of T As IComparable(Of T)) _ : Implements IEnumerable(Of T) ' Funktionen für die abgeleiteten Klassen: Hinzufügen & Durchlaufen Public MustOverride Function Add(ByVal x As T) As BinaryTree(Of T) Protected MustOverride Function GetElements() As IEnumerable(Of T) ' IEnumerable unterstützen Protected Function GetEnumerator() As IEnumerator(Of T) _ Implements IEnumerable(Of T).GetEnumerator Return GetElements.GetEnumerator() End Function Private Function GetEnumerator1() As IEnumerator _ Implements IEnumerable.GetEnumerator Return GetEnumerator() End Function End Class ' Konstruktorfunktionen: ' Einen leeren Baum erstellen Public Function Leaf(Of T As IComparable(Of T))() As BinaryTree(Of T) Return New LeafNode(Of T)() End Function ' Einen Baum aus zwei Teilbäumen und einer Wurzel zusammensetzen Public Function Node(Of T As IComparable(Of T))(ByVal value As T, _ ByVal left As BinaryTree(Of T), _ ByVal right As BinaryTree(Of T)) As BinaryTree(Of T) Return New TreeNode(Of T)(value, left, right) End Function ' Implementierungen der Basisklassen ' Implementierung für einen leeren Baum Private Class LeafNode(Of T As IComparable(Of T)) _ : Inherits BinaryTree(Of T) ' Neuen Baum erzeugen mit x als Wurzelelement Public Overrides Function Add(ByVal x As T) As BinaryTree(Of T) Return Node(x, Leaf(Of T)(), Leaf(Of T)()) End Function ' Keine Elemente zum Zurückgeben vorhanden Protected Overrides Function GetElements() As _ System.Collections.Generic.IEnumerable(Of T) Return New T() {} End Function End Class ' Implementierung für einen Baumknoten Private Class TreeNode(Of T As IComparable(Of T)) : Inherits BinaryTree(Of T) Private ReadOnly m_Value As T Private ReadOnly m_Right, m_Left As BinaryTree(Of T) Public Sub New(ByVal x As T, ByVal left As BinaryTree(Of T), _ ByVal right As BinaryTree(Of T)) m_Value = x : m_Left = left : m_Right = right End Sub ' Linker Teilbaum & Wurzel & rechter Teilbaum Protected Overrides Function GetElements() As _ System.Collections.Generic.IEnumerable(Of T) Return m_Left.Concat(New T() {m_Value}).Concat(m_Right) End Function ' Rekursives Einfügen Public Overrides Function Add(ByVal x As T) As BinaryTree(Of T) If x.CompareTo(m_Value) < 0 Then ' Wenn x kleiner als die Wurzel ist, in den linken ' Teilbaum einfügen Return Node(m_Value, m_Left.Add(x), m_Right) Else ' ... sonst in den rechten Return Node(m_Value, m_Left, m_Right.Add(x)) End If End Function End Class End Module Module Module1 Sub Main() ' Zufällige Daten erzeugen Dim random As New Random() Dim data As IEnumerable(Of Integer) = _ From i In Range(1, 25) Select random.Next(1, 10) ' Den Baum schrittweise aus den Daten zusammenbauen Dim sortedTree As BinaryTree(Of Integer) = Leaf(Of Integer)() For Each i As Integer In data sortedTree = sortedTree.Add(i) Next ' Ausgeben Console.WriteLine("Daten: ") For Each x As Integer In data Console.WriteLine(x) Next Console.WriteLine("Sortierte Daten: ") For Each x As Integer In sortedTree Console.WriteLine(x) Next Console.ReadLine() End Sub End Module
Ihre Meinung
Falls Sie Fragen zu diesem Artikel haben oder Ihre Erfahrung mit anderen Nutzern austauschen möchten, dann teilen Sie uns diese bitte in einem der unten vorhandenen Themen oder über einen neuen Beitrag mit. Hierzu können sie einfach einen Beitrag in einem zum Thema passenden Forum anlegen, welcher automatisch mit dieser Seite verknüpft wird.