✔ Quicksort

[noreya]

Hallo,
ich habe ein Arry zu sortieren und wollte dafür quicksort nehmen. Jetzt frage ich mich aber gerade ob das in meinem Fall überhaupt geht, da mein Array einen benutzerdefinierten Typ hat und ich nach einer dieser Eigenschaften sortieren will:

Ausgangssituation:

Type meinTyp
    name
    anz
    summe
end type

dim a() as meinTyp

Ziel
Das array a wird im Laufe des Codes mit Werten gefüllt. Es wird städig verädert - daher kann ich es erst hinterher sortieren. Sortiert werden soll einmal nach a(x).anz und einmal nach a(x)summe.

Hat jemand eine Idee? Geht das mit Quicksort überhaupt? Was für Alternativen gibt es?

Danke und Gruß
noreya*

 

[Shakie]

Warum sollte es mit "Quicksort" nicht gehen? Statt direkt den Wert im Array-Element zu vergleichen vergleichst du halt a(x).anz miteinander, wie du schon geschrieben hast.

 

[noreya]

hm. das versuche ich die ganze zeit. aber noch hab ich ne Endlosschleife...

Function quicksort(l As Long, r As Long, a() As typ_AG)    
    Dim i, j, m As Long
    Dim t() As typ_AG
    ReDim Preserve t(1)
    i = l
    j = r
    m = UBound(a) \ 2
    
    Do
        Do While a(i).Summe < a(m).Summe
            i = i + 1
        Loop
        Do While a(m).Summe < a(j).Summe
            j = j - 1
        Loop
        If a(i).Summe <= a(j).Summe Then
            t(1) = a(i)
            a(i) = a(j)
            a(j) = t(1)
            i = i + 1
            j = j - 1
        End If
    Loop Until i > j
    
    If l < j Then Call quicksort(l, CLng(j), a())
    If i < r Then Call quicksort(CLng(i), r, a())
End Function

 

[noreya]

puh. also ich komm echt nicht weiter.
Die Endlosschleife entseht durch folgendes:

a(i).Summe < a(m).Summe

trifft nicht zu (6000 < 5000)

a(m).Summe < a(j).Summe

trifft auch nicht zu (5000 < 0)

a(i).Summe <= a(j).Summe

trifft auch nicht zu (6000 <= 0)


Also trifft wird keine Veränderung mehr durchgeführt.

Bitte helft mir!

 

[noreya]

aaah!
Jetzt bin ich einen Schritt weiter und trotzdem am Ende
"nicht genügend Speicher!"
Was nun?

mein Code sieht jetzt so aus:

Function quicksort(l As Long, r As Long, a() As typ_AG)
    Dim i, j, m As Long
    Dim t() As typ_AG
    ReDim Preserve t(1)
    i = l
    j = r
    m = UBound(a) \ 2
    
    Do
        Do While a(i).Summe < a(m).Summe
            i = i + 1
        Loop
        Do While a(j).Summe > a(m).Summe
            j = j - 1
        Loop
        If a(i).Summe <= a(j).Summe Then
            t(1) = a(i)
            a(i) = a(j)
            a(j) = t(1)
            i = i + 1
            j = j - 1
        End If
    Loop Until a(i).Summe > a(j).Summe
    
    If l < j Then Call quicksort(l, CLng(j), a())
    If i < r Then Call quicksort(CLng(i), r, a())
End Function

Verändert ist nur die Zeile

 Loop Until a(i).Summe > a(j).Summe

 

[Shakie]

Hier findest du einen QuickSort-Algorythmus: http://vb-tec.de/qsort.htm
Schau dir einfach mal an, wie das da gemacht ist.
Oder:

 

[noreya]

Bald geb ich auf.

hat mich ja überhaupt erst auf quicksort gebracht. Und Beispiele finden ist kein Problem - aber Erklärungen! Oder Hilfen, wenn es eben nicht geht.

Bei mir läuft es jetzt zwar (endlich) - aber es sortiert nicht bis zum Ende durch. In kurzen Datenfeldern sieht es so aus als hätt es geklappt, aber umso länger die Liste wird um so mehr Fehler sind drin...

Function quicksort(MinBound As Long, MaxBound As Long, a() As typ_AG)
    Dim MinIndex, MaxIndex, m As Long
    Dim t() As typ_AG
    ReDim Preserve t(1)
    MinIndex = MinBound
    MaxIndex = MaxBound
    m = (MinBound + MaxBound) \ 2
    
    Do
        Do While a(MinIndex).SummeProjekte < a(m).SummeProjekte
            MinIndex = MinIndex + 1
        Loop
        Do While a(MaxIndex).SummeProjekte > a(m).SummeProjekte
            MaxIndex = MaxIndex - 1
        Loop
        If MinIndex <= MaxIndex Then
            t(1) = a(MinIndex)
            a(MinIndex) = a(MaxIndex)
            a(MaxIndex) = t(1)
            MinIndex = MinIndex + 1
            MaxIndex = MaxIndex - 1
        Else
            Exit Do
        End If
    Loop
    If MinBound < MaxIndex Then Call quicksort(MinBound, CLng(MaxIndex), a())
    If MinIndex < MaxBound Then Call quicksort(CLng(MinIndex), MaxBound, a())

End Function

Mein Fehler von dem Problem oben lag an der Bedingung MinIndex <= MaxIndex -> Hier hatte ich anstelle des Indexes den Wert verglichen.

Hat noch irgendjemand eine Idee, wie ich Quicksort jetzt auch zum sortieren bringe? Es müssen ja keine Lösungen sein - nur ein Ansatz, ich bin ziemlich ratlos.

Danke

 

[mage]

Bei Wikipedia gibt es eine Beispielimplementierung in Pseudocode.

Die C Implementation entspricht deiner Implementierung.
Der grösste Unterschied ist der Abbruch mit exit Do in deiner Schleife. Die fehlt bei dir. Daher bricht er vermutlich zu früh die Sortierung ab.

 

[deepthroat]

Hi.

Es gibt einen ganz entscheidenden Unterschied zwischen der C Implentierung und dem Code von noreya: in C wird der Wert des Pivot Elements gespeichert, bei dir nur der Index des Pivot Elements auf den du immer wieder zugreifst. Allerdings kann auch das Pivotelement selbst verschoben werden und dann hast du plötzlich ein ganz anderes Element mit dem du vergleichst.

Du kannst dir ja nochmal einfach den Code auf den Shakie gelinkt hat anschauen.

Gruß

 

[noreya]

Danke für eure Antworten und Hinweise!

Ich bin nach 3 Tagen tatsächlich dahinter gekommen:

Erst mal hab ich das mit dem Pivot-Element geändert - danke deepthroat!

Dann gabs aber wieder einen Speicherüberlauf.
Lösung:

m hatte den Dateityp Long. Die Zahl in m hatte aber Kommastellen.
Jetzt ist m Double und alles geht

Grüße
noreya*