Zahlenwerte mit QuickSort in Spalte sortieren

Beiträge zum Forumthread

Beiträge zu diesem Forumthread

Betreff

Datum

Anwender

Hallo Timo!
Quicksort ist bei mir schon ein 2-3 Semester her. Ich hatte damals auch einen Quicksort für VBA programmiert. Leider nicht dokumentiert und mit saumäßigen Parameterübergaben versehen. Vielleicht hilft es Dir weiter.
Schönen Gruß, Tobi
http://www.tobiasschmid.de/

Call Quicksort(Data, 1, UBound(Data))

Private Function Quicksort(Data, links, rechts)
Dim Teiler As Long
If rechts > links Then
    Teiler = Teile(Data, links, rechts)
    Call Quicksort(Data, links, Teiler - 1)
    Call Quicksort(Data, Teiler + 1, rechts)
End If
End Function

Private Function Teile(Data, links, rechts)
Dim Index As Long
Dim i As Long
Index = links
For i = links To rechts - 1
    If Data(i) <= Data(rechts) Then
        Call Tausche(Data, Index, i)
        Index = Index + 1
    End If
Next
Call Tausche(Data, Index, rechts)
Teile = Index
End Function

Private Sub Tausche(Data, i, j)
Dim Temp As Double
Temp = Data(i)
Data(i) = Data(j)
Data(j) = Temp
End Sub

Hallo Timo!
Mit diesem Code sollte es klappen. Die Dokumentation ist aber immer noch sehr dürftig.
Hinweis:
Es kann passieren, dass das Programm mit der Meldung "zu wenig Speicher" abbricht. Problem ist, das Quicksort ein rekursiver Sortieralgorithmus ist und unter ungünstigen Bedingungen zu viele Rekursionen notwendig werden um die Liste zu sortieren. Siehe hierzu auch Wikipedia. http://de.wikipedia.org/wiki/Quicksort


Im ungünstigsten Fall ist die Anzahl der Rekursionen nur durch die Listenlänge n beschränkt,  _
was einen
Stapel der Größe \mathcal{O}(n ) erfordert. Dies kann bei langen Listen zu einem Stapelüberlauf  _
führen. Es
gibt vielfältige Modifikationen des Algorithmus um dieses Problem zu lösen bzw. die  _
Wahrscheinlichkeit des
Auftretens zu vermindern[2]:
* Endrekursionsbeseitigung (siehe nachfolgenden Pseudocode)
* eine ausgewogenere Wahl des Pivotelements (Median von Drei)
* Wahl eines zufälligen Pivotelements, was systematische Probleme durch die ursprüngliche  _
Anordnung der Elemente vermeidet
* Vermeidung von Teilisten mit weniger als zwei Elementen (ergibt, wenn auch das  _
Pivotelement aus den Teillisten genommen wird, die maximale Rekursionstiefe n / 3)

Option Explicit
Private Daten() As Double
Private rng As Range
Sub Main()
    'Daten aus den Zellen AA22 bis AA8780 in das Datenfeld Daten kopieren
    Set rng = Range("AA22:AA8780")
    Einlesen
    'Daten mit Quicksort sortieren
    Call Quicksort(Daten, 1, UBound(Daten))
    'Daten wieder ins Excel-Sheet zurückschreiben
    Set rng = Range("AB22:AB8780")
    Auslesen
    'Kurze Meldung wenn fertig
    Debug.Print "fertig"
End Sub
Private Sub Einlesen()
    Dim i As Long
    ReDim Daten(rng.Rows.Count)
    'Zelleninhalte schnellstmöglich nach VBA lesen
    For i = 1 To UBound(Daten)
        Daten(i) = rng(i, 1)
    Next
End Sub
Private Sub Auslesen()
    Dim i As Long
    Dim var As Variant
    'VBA-Daten schnellstmöglich in Zellen schreiben
    var = rng
    For i = 1 To UBound(Daten)
        var(i, 1) = Daten(i)
    Next
    rng = var
End Sub
Private Function Quicksort(Data, links, rechts)
    Dim Teiler As Long
    If rechts > links Then
        Teiler = Teile(Data, links, rechts)
        Call Quicksort(Data, links, Teiler - 1)
        Call Quicksort(Data, Teiler + 1, rechts)
    End If
End Function
Private Function Teile(Data, links, rechts)
    Dim Index As Long
    Dim i As Long
    Index = links
    For i = links To rechts - 1
        If Data(i) <= Data(rechts) Then
            Call Tausche(Data, Index, i)
            Index = Index + 1
        End If
    Next
    Call Tausche(Data, Index, rechts)
    Teile = Index
End Function
Private Sub Tausche(Data, i, j)
    Dim Temp As Double
    Temp = Data(i)
    Data(i) = Data(j)
    Data(j) = Temp
End Sub

Ich hoffe, ich konnte Dir helfen, Tobi
http://www.tobiasschmid.de/

Beliebteste Forumthreads (12 Monate)

Zahlenwerte mit QuickSort in Spalte sortieren

8
Beiträge zum Forumthread

Beiträge zu diesem Forumthread

318 Forumthreads zu ähnlichen Themen

Beliebteste Forumthreads (12 Monate)

Beliebteste Forumthreads (12 Monate)

Zahlenwerte mit QuickSort in Spalte sortieren

8 Beiträge zum Forumthread Beiträge zu diesem Forumthread

318 Forumthreads zu ähnlichen Themen

VBA Beispiele zu verwandten Themen

Beliebteste Forumthreads (12 Monate)

Beliebteste Forumthreads (12 Monate)

8
Beiträge zum Forumthread

Beiträge zu diesem Forumthread