Die Community zu .NET und Classic VB.
Menü

Tipp-Upload: VB.NET 0300: Teilweises Sortieren - N-t größtes Element bestimmen

 von 

Ü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.

Zurück zur Übersicht

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

Schwierigkeitsgrad 2

Verwendete API-Aufrufe:

Download:

Download des Beispielprojektes [9,31 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 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

Tipp-Kritiken - Dario 16.08.2008 20:12

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