Tipp-Upload: VB.NET 0300: Teilweises Sortieren - N-t größtes Element bestimmen
von Dario
Ü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:
NthElement, quicksearch, partition
Der Vorschlag wurde erstellt am: 16.08.2008 16:54.
Die letzte Aktualisierung erfolgte am 16.08.2008 16:54.
Beschreibung
Möchte man das Maximum eines Arrays berechnen, geht das recht einfach. Möchte man nun aber z.B. das fünfhunderachzigst-größte Element bestimmen, ist das mit einigem Rechenaufwand verbunden, v.A. wenn das Array entsprechend groß ist. Eine intuitive Variante wäre, das Maximum zu suchen, zu entfernen und das Selbe für den Rest wieder durchzuführen - n mal. Bei kleinen Werten oder Arrays geht das, aber wie bei SelectionSort - dem ähnelt dieses Prinzip - ist die Laufzeit bald katastrophal. Auch das gesamte Array zu sortieren ist unnötig.
Ein sehr guter Ansatz basiert auf QuickSort. Das Array wird auch mit einem Pivotelement in 2 Hälften aufgeteilt (Partition-Methode), aber es wird jetzt immer nur der einen Hälfte weitergerechnet, in dem sich das gesuchte Element befindet.
Dieser Tipp enthält eine zufallsoptimierte Implementierung dieses Suchsystems und die langsamere Variante zum Vergleich.
|
Schwierigkeitsgrad
|
Verwendete API-Aufrufe: |
Download: |
' 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 NthElement.sln ----------- ' ---------- Anfang Projektdatei NthElement.vbproj ---------- ' ----------------- Anfang Datei Module1.vb ----------------- Option Strict On Imports System.Runtime.CompilerServices Module Module1 Private Rand As Random = New Random ' Tauschen Public Sub Swap(Of T)(ByRef A As T, ByRef B As T) Dim Tmp As T = B B = A A = Tmp End Sub ' So einfach ist übrigens QuickSort mit Partition <Extension()> Sub QuickSort(Of T)(ByVal Data() As T, ByVal Left As Integer, ByVal Right _ As Integer, ByVal Comp As Comparison(Of T)) If Left >= Right Then Return Dim Lim = Data.Partition(Left, Right, Comp) Data.QuickSort(Left, Lim, Comp) Data.QuickSort(Lim + 1, Right, Comp) End Sub ''' <summary> ''' Teilt in einem Array die Elemente zwischen Left und Right so auf, dass alle, die kleiner als ein sog. Pivotelement sind, ''' vor diesem stehen und alle größeren hinter ihm. ''' </summary> ''' <typeparam name="T">Typ des Arrays</typeparam> ''' <param name="Data">Array mit den Daten</param> ''' <param name="Left">Linke Grenze</param> ''' <param name="Right">Rechte Grenze</param> ''' <param name="Comp">Vergleichsfunktion</param> ''' <returns>Position des Endes der 1. beim Aufteilen entstandenen Sequenz</returns> ''' <remarks>Zufallsoptimierte Version von Partition und Grundlage von QuickSort.</remarks> <Extension()> Public Function Partition(Of T)(ByVal Data() As T, ByVal Left As Integer, _ ByVal Right As Integer, ByVal Comp As Comparison(Of T)) As Integer ' Pivotelement Dim Pivot As T = Data(Rand.Next(Left, Right + 1)) Do ' "Unteres" Element suchen, dass die Bedingung verletzt Do While Comp(Data(Left), Pivot) < 0 Left += 1 Loop ' "Oberes" Element suchen, dass die Bedingung verletzt Do While Comp(Pivot, Data(Right)) < 0 Right -= 1 Loop If Left < Right Then ' Die beiden Elemente tauschen und die Suchpositionen weiterrücken Swap(Data(Left), Data(Right)) Left += 1 Right -= 1 Else ' Fertig - Grenze der beiden Sequenzen zurückgeben Return Right End If Loop End Function ' Rekursiv n. größtes Element ermitteln ... <Extension()> Function NthElement(Of T)(ByVal Data() As T, ByVal Left As Integer, ByVal _ Right As Integer, ByVal n As Integer, ByVal Comp As Comparison(Of T)) As T ' Wenn gültige Grenzen vorliegen If Left < Right Then ' Daten aufteilen - Alle Elemente im vorderen Teil sind kleiner als die im hinteren Dim Lim = Data.Partition(Left, Right, Comp) ' Größe des hinteren Teiles Dim Size2nd = Right - Lim If Size2nd >= n Then ' Wenn der hintere entstandene Teil größergleich n ist, dann muss das n-t ' größte Element dortdrin liegen Return Data.NthElement(Lim + 1, Right, n, Comp) Else ' OK, probieren wir's im vorderen Teil - Wenn im hinteren Teil 2 Elemente ' sind, dann sind sie größer als alle im vorderen Teil ' Folglich muss man die gewünschte Stellung des gesuchten Elementes ' anpassen. In dem Fall sucht man hier nur noch das n-2. Element Return Data.NthElement(Left, Lim, n - Size2nd, Comp) End If ElseIf n = 1 Then ' Wir haben das Element gefunden Return Data(Left) Else ' Das sollte nicht passieren Return Nothing End If End Function ''' <summary> ''' Ermittelt das n. größte Element aus einem Array. Das Prinzip ähnelt QuickSort ''' </summary> ''' <typeparam name="T">Typ des Arrays</typeparam> ''' <param name="Data">Das Array</param> ''' <param name="n">Welches Element soll gefunden werden</param> ''' <param name="Comp">Optionaler Vergleichsoperator - Automatisch, wenn Elemente IComparable sind</param> ''' <returns>Gibt das n. größte Element zurück</returns> <Extension()> Function NthElement(Of T)(ByVal Data() As T, ByVal n As Integer, Optional _ ByVal Comp As Comparison(Of T) = Nothing) As T Return Data.NthElement(0, Data.Count - 1, n, CType(IIf(Comp Is Nothing, New _ Comparison(Of T)(Function(a As T, b As T) Comparer(Of T).Default().Compare(a, _ b)), Comp), Comparison(Of T))) End Function ''' <summary> ''' Ermittelt das n. größte Element aus einem Array. Das Prinzip ähnelt SelectionSort ''' </summary> ''' <typeparam name="T">Typ des Arrays</typeparam> ''' <param name="Data">Das Array</param> ''' <param name="n">Welches Element soll gefunden werden</param> ''' <param name="Comp">Optionaler Vergleichsoperator - Automatisch, wenn Elemente IComparable sind</param> ''' <returns>Gibt das n. größte Element zurück</returns> <Extension()> Function NthElement2(Of T)(ByVal Data() As T, ByVal n As Integer, Optional _ ByVal Comp As Comparison(Of T) = Nothing) As T Comp = CType(IIf(Comp Is Nothing, New Comparison(Of T)(Function(a As T, b As T) _ Comparer(Of T).Default().Compare(a, b)), Comp), Comparison(Of T)) Dim MaxIndex, i As Integer For i = Data.Count - 1 To Data.Count - n Step -1 MaxIndex = i For j = 0 To i If Comp(Data(j), Data(MaxIndex)) > 0 Then MaxIndex = j Next Swap(Data(i), Data(MaxIndex)) Next Return Data(i + 1) End Function Sub Main() Const Max As Integer = 42000 Dim n As Integer = Rand.Next(1, Max) Dim Data = (From i In Enumerable.Range(1, Max) Select Rand.Next(1, Max)).ToArray Console.Write("Partition-Variante: Drücken sie 'Enter'") Console.ReadLine() Console.WriteLine("...") Console.WriteLine("Das {0}-t kleinste Element lautet: {1}", n, Data.NthElement(n, _ Function(a, b) b - a)) Console.WriteLine() Console.Write("Selection-Variante: Drücken sie 'Enter'") Console.ReadLine() Console.WriteLine("...") Console.Write("Das {0}-t kleinste Element lautet: {1}", n, Data.NthElement2(n, _ Function(a, b) b - a)) Console.ReadKey() End Sub End Module ' ------------------ Ende Datei Module1.vb ------------------ ' ----------- Ende Projektdatei NthElement.vbproj ----------- ' ------------ Ende Projektgruppe NthElement.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.
Folgende Diskussionen existieren bereits
Um eine Diskussion eröffnen zu können, müssen sie angemeldet sein.