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:

Code :

1 2 3 4 5 6 7

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*

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.

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

Code :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

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

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

Code :

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

trifft nicht zu (6000 < 5000)

Code :

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

trifft auch nicht zu (5000 < 0)

Code :

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

trifft auch nicht zu (6000 <= 0)


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

Bitte helft mir!

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

mein Code sieht jetzt so aus:

Code :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

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

Code :

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

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

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

Code :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

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

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.

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ß

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*