stack-overflow bei quicksort

[upsidedown]

Is vielleicht nicht das richtige board dafür, aber schaden kanns ja nicht. Vielleicht hat ja doch jemand eine Idee..

Bei mir klemmts zur Zeit bei folgendem:

Ich schreib zur Zeit an einem Programm (C++) bei dem ständig sehr grosse arrays (von ein paar hundert bis zu einigen zehntausend bis knapp 100k Elementen) sortiert werden müssen. Dabei hab ich zwei Probleme:

1. da das [U]sehr[\U] häufig geschieht (geschätzte Laufzeit bei dem vollständigen später zu verarbeitenden Datensatz: 20-30h...) bin ich zwingend auf einen schneller Sortieralgorithmus angewiesen.

2. auf die zu sortierende Datenstruktur kann ich keinen fertig implementierten qsort anwenden.

Bis jetzt habe ich ein Lehrbuchbeispiel zum Quicksort an die Datenstruktur angepasst was auch ganz passabel funktioniert. Bei bestimmten Datensätzen kommt es aber zu einem stack-overflow, was ziemlich lästig ist, da damit mehrere Stunden Berechnungen verloren gehen.

Als Compiler verwende ich WEdit Win32 Ver 3.3, da MS-VC++ das Programm nicht kompilieren kann - der Debugger funktioniert allerdings.

Irgendjemand eine praktische Idee das Problem in den Griff zu bekommen oder zumindest eine brauchbare Abschätzung ab welcher Arraygrösse der stackoverflow auftritt (einzelne Datensätze dürfen übergangen werden)?

:help: :help: :help: :help: :help:
Das wirklich blöde ist nämlich, dass das Programm gebraucht wird (aus Spass anner Freud würd ich nicht 1400++ Zeilen Code zusammenstoppeln...)

Gruß,
UpsideDown

[DYSTOPIC]

Darf ich fragen wofür du sowas brauchst?

Beitragen zu deinem Problem kann ich allerdings nichts, bin dummer Schüler der qsort nur von Delphi aus nem Info GK kennt.

[Lim_Dul]

Uff ein harter brocken :)

Ich habe auf Anhieb erstmal mehrere Ideen, welche davon umsetzbar sind weiß ich nicht:

Quicksort arbeitet ja rekursiv, bis die Teilmengen direkt sortierbar, bei den standardbeispielen wird meines Wissens das Array immer wieder geteilt, bis man 2 oder 3 Elemente hat. Vielleicht würde es helfen, diese Grenze auf 100 Elemente oder so zu setzen, und diese Elemente dann nach einer anderen, nicht rekursiven Methode zu sortieren.

Eigentlich dürfte bei 100k Datensätzen noch lange kein Stackoverflow auftreten, es sei den der Compiler baut Bockmist, oder du legst viel zu viele Kopien deiner Daten an. Normalerweise wird bei einer rekursiven Funktion soviel nicht auf den Stack geworfen, als das man einen Overflow produzieren könnte.

Worauf ich dein Quicksort jetzt mal überprüfen würde, wäre a) was wird an Variablen innerhalb der Funktion erzeugt, kann man die irgendwie einsparen.
b) Wie werden die Parameter übergeben (Obowhl da keine Fehler sein dürften, sonst sollte Quicksort nicht laufen)

Ich würde dir raten, mal einen anderen Compiler auszuprobieren (habe leider jetzt keinen Link zur Hand).
Oder guck mal, ob man in dem Compiler das Memory Model umstellen kann, so das mehr Stack zur Verfügung steht.

Wenn es nicht zu groß ist, würde ich gerne mal die Quicksort Funktion sehen.

Das waren so meine ersten Ideen, vielleicht finde ich ja den zündenden Gedanken später ;)

[upsidedown]

int partition(float *Array[], int ui, int oi)
{ int i = ui, j = oi; /* Laufindizes */

//float temp[7]; /* für Austausch zweier Elemente */
float *temp;

float comp = Array[ui][3]; /* Vergleichselement (Schranke) */

while (i <= j)
{ /* nächstes Element > comp von links suchen (im linken Teil) */
while (i <= j && Array[i][3] <= comp)
i++;
/* nächstes Element < comp von rechts suchen (im rechten Teil) */
while (j >= i && Array[j][3] >= comp)
j--;
if (i < j)
{
temp=Array[i];
Array[i]=Array[j];
Array[j]=temp;
i++;
j--;
}
}
i--;
/* setze Vergleichselement (Schranke) zwischen beide Teile */
temp=Array[ui];
Array[ui]=Array[i];
Array[i]=temp;
return(i);
}

void qsortcr(float *Array[], int ui, int oi)
{ int idx; /* Schranke einer Zerlegung */

if (ui >= oi) /* Abbruchbedingung der Rekursion */
return;
else
{ idx = partition(Array, ui, oi);
qsortcr(Array, ui, idx - 1); /* linken Teil rekursiv sortieren */
qsortcr(Array, idx + 1, oi); /* rechten Teil rekursiv sortieren */
}
}

Kurze Erläuterung zur Datenstruktur:

*Array[] wird nach [3] zeilenweise sortiert. Die Zeilen sind einzeln gepointert, weswegen ich sie auch in partition einfach tauschen kann.

Den qsort hab ich einfach aus irgendeinem übungsmanuskript rauskopiert und hingebogen. Und eigentlich funktioniert es ja auch.