seltsames problem mit quicksort

[doomcalyptica]

hallo, in meiner schzule haben wir das thema rekursion, sortieralgorithmen dran gehabt. den quicksort algorythmus haben wir mit delphi ausprobiert und nun wollte ich ihn mit C probieren (nur mal um einen okleinen benchmark zu bauen, um zu schauen was wohl schnelle r is ob delphi oder C) ... leider hat das programm bei C ein etwas seltsames laufzeitverhalten -> das array bleib hier nach dem aufruf von quicksort in main "unbeschrieben" ... ich vermute mal, das ich die sache mit den pointer in einem rekursiven aufruf einer funktion als argument nich anwenden darf.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX 10

// 5 78 50 22 48

void quicksort(int ug, int og, int*feld) {
int pivot;
int rechts=og;
int links=ug;
int swap;

pivot=feld[og/2];

do {
while(feld[links]<=pivot)links++;
while(feld[rechts]>=pivot)rechts--;

if(links<rechts) {
swap=feld[links];
feld[links]=feld[rechts];
feld[rechts]=swap;
links++;
rechts--;
printf("debug\n");
}

} while (!(rechts<links));

if(links<og) quicksort(links,og,feld);
if(ug<rechts) quicksort(ug,rechts,feld);
}

int main() {
srand(time(0));
int i=0;
int feld[MAX];

for(i; i<MAX; i++)
printf("%d\n",feld[i]=rand()%100);
printf("\n");
quicksort(0,MAX-1,feld);
for(i=0; i<MAX; i++)
printf("%d\n",feld[i]);

return 0;
}
kann mir jemand helfen, oder besser, kann jemand bitte den fehler beseitigen ... ich weis bei dieser sache wirklich nicht weiter ...

ps: das prgramm lasst sich in der schule zwar ausführen, doch kommt bei der funktion quicksort es zu einem "segmentation fault"
wobei bei mir @ home quicksort erfolgreich aufgerufen wurde, dennoch "kryptische" für mich sinnlose zahlen (alle dieselben und im negativen bereich) im ganzen array auftreten.

[doomcalyptica]

ups: sorry ich hab noch einen symantik fehler drinn

pivot=feld[(og+ug)/2];
dennoch habe ich ein segmentation fault
kanne s sein, das ich die zeiger geschichte nicht in rekursiven programmen anwenden darf ?

[peschmae]

Also wenns dir nur um die Funktionalität geht hat C auch ne qsort() Funktion in der Standard library.



#include <stdlib.h>

void qsort(void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *));


Den konkreten Code hab ich jetzt nicht so genau angeguckt, aber schon nur mal die beiden Schliefen


while(feld[links]<=pivot)links++;
while(feld[rechts]>=pivot)rechts--;


finde ich *sehr* merkwürdig. Ich meine da machst du ja nichts ausser rumzählen...

MfG Peschmä

[doomcalyptica]

richtig, ich muss auch das nächst großer element bzw das nächst kleinere element finden, um später tauschen zu können (vorsortierung, damit rechts vom pivot alles großer und links vom pivot alles kleiner ist)
aber das ist nicht mein problem mit dem "segmentation fault" ^^

[peschmae]

Achso, stimmt.

Na dann wirf mal den Debugger an...dem Backgrace nach hast du vergessen dass du mal aufhören willst, das sind >2000 rekursive Aufrufe :D

(Das int* Zeugs scheint mir übrigens ok zu sein, der Fehler ist wohl woanders)

MfG Peschmä

[locus vivendi]

Also das ganze Programm durchzuschauen habe ich jetzt keine Lust, aber der Ausschnitt unten ist schon mal fehlerhaft. Früher oder später wird da versucht werden ein Element außerhalb des Arrays zu lesen.


pivot=feld[og/2];

do {
while(feld[links]<=pivot)links++;

[Joghurt]

while(feld[links]<=pivot)links++;
while(feld[rechts]>=pivot)rechts--;Das sollte schonmal
while (links<og && feld[links]<= pivot) links++;
while (rechts>ug && feld[rechts] >= pivot) rechts--;heißen, sonst läufst du über das Arrayende/-anfang hinaus, falls kein Wert größer/kleiner als das Pivotelement ist.