28. Juni 201114 j Moinsen, ich hab da leider mal wieder n Problem... in C-Programmieren -.- diesmal mit der Umsetzung von quicksort ohne qsort aus der stdlib... folgende Struktur liegt zu Grunde: typedef struct sP { struct sPD *pPD; }sP; typedef struct sPD { char cName[50]; }sPD; nun habe ich ein Array dieser Form: sP *arP = (sP*)malloc(100000*sizeof(sP)); Sprich ich habe ein Array aus Pointern die jeweils auf einen Datensatz Zeigen (dahinter hängt noch was dran, ist ja aber für das sortieren egal... sprich ich muss die Pointer sortieren nach vergleich der Datensätze auf die sie zeigen... BubbleSort klappt... qSort stdLib auch... zb ist für qsort() dies hier meine Vergleichsfunktion: int vergleichP(const void *Str1, const void *Str2) { sP *pP1 = (sP *)Str1; sP *pP2 = (sP *)Str2; return strcmp(pP1->pPD->cName, pP2->pPD->cName); } hoffe ihr könnt mir auf die Sprünge helfen...
28. Juni 201114 j Moin. sP *arP = (sP*)malloc(100000*sizeof(sP)); Sprich ich habe ein Array aus Pointern die jeweils auf einen Datensatz Zeigen (dahinter hängt noch was dran, ist ja aber für das sortieren egal... Sprich Du hast ein Array von 100000 Zeigern auf uninitialisierte sPD.
28. Juni 201114 j ok da sieht das so aus... aber keine Angst ich sorge schon dafür das ein sPD genügend Speicher zugewiesen bekommt.. und zwar in der Funktion die mir jeweils einen sPD mit Daten füllt und danach den Pointer auf dieses Element im Pointer Array speichert.. Bearbeitet 28. Juni 201114 j von Dionysos211
28. Juni 201114 j Hm... okay, das wäre ein hilfreicher Zusatz gewessen, aber kann es auch sein das strcmp char Zeiger will und keine char Arrays?
28. Juni 201114 j ? also die Vergleichsfunktion oben nutze ich lediglich für qsort() aus der stdlib.h ... das funktioniert auch alles nur muss ich mir jetzt quasi ein my_quicksort() basteln... und zu deiner strcmp() Frage... char zeiger ist nicht anderes als char[] ... sprich ich übergebe die adresse vom ersten Element des Strings... und strcmp() vergleicht Element für Element mit dem andern String bis ein /0 gelesen wurde... strcmp liefert: Element1 = Element2 rerun 0 Element1 > Element2 return 1 Element1 < Element2 return -1
28. Juni 201114 j das funktioniert auch alles nur muss ich mir jetzt quasi ein my_quicksort() basteln...Dann zeig doch mal, was du bis jetzt hast.
28. Juni 201114 j bin grad am rumtesten... derweil hier mal mein bubble... void bubbleP(sP *arP, int lenP) { int i; sPD *pTempPD = (sPD*) malloc(sizeof(sPD)); while(lenP--) for(i = 1; i <= lenP; i++) if((strcmp(arP[i-1].pPD->cName, arP[i].pPD->cName)) > 0) { pTempPD = arP[i].pPD; arP[i].pPD = arP[i-1].pPD; arP[i-1].pPD = pTempPD; } } brauch für 100.000 elemente satte 245 sekunden -.- scheint mir grad n bischen zu happig achja lenP ist die länge des Pointer array was zur laufzeit der main() ermittelt wird..
28. Juni 201114 j sodelle... ich hab da jetzt was zusammen geschustert... und rumprobiert bis zum get no... ich weiß wie der Quicksort an für sich laufen soll... und hab irgendwie das gefühl ich mach was falsch.. aber es funkioniert.. Quick Sort: - ermittle median(pivot) element (links + rechts)/2 dabei steht links für das erste und rechts für das letzte element des "Arrays" oder beim Rekursiven Aufruf "Teil-Array" - teile jetzt nach links und rechts auf - links kleiner gleich (also zweiter string ist "größer" oder gleich string 1) => findest du eins was nicht passt hold on und geh zu nächsten while - recht größer gleich (also erster string ist "größer" oder gleich string 1) => findest du eins was nicht passt hold on und TAUSCHE mach das so lange wie du falsche elmente findest.. rufe nun rekursiv auf und bis weniger als 2 elemente da sind... -------------- glaub so müsste das richtig sein... und so hab ich das jetzt umgesetzt.. btw darf ich das mit der for schleife wegen dem break so handeln ? void quicksort( int links, int rechts, sP *arP) { int l, r; sP pivot, temp; if( rechts > links) { pivot = arP[rechts]; l = links-1; r = rechts; for( ; { while((r > l) && (strcmp(arP[++l].pPD->cName, pivot.pPD->cName) <= 0)) ; while((r > l) && (strcmp(arP[--r].pPD->cName, pivot.pPD->cName) >= 0)) ; if( l >= r) break; temp = arP[l]; arP[l] = arP[r]; arP[r] = temp; } arP[rechts] = arP[l]; arP[l] = pivot; quicksort( links, l-1, arP); quicksort( l+1, rechts, arP); } } [/code] Bearbeitet 28. Juni 201114 j von Dionysos211
29. Juni 201114 j und hab irgendwie das gefühl ich mach was falsch.. aber es funkioniert..Wenn es funktioniert, was ist dann das Problem? - ermittle median(pivot) element (links + rechts)/2(links + rechts)/2 ist kein Median, das ist einfach das Element in der Mitte. Aber selbst das setzt du in deinem Code nicht um, da nimmst du immer das rechte Element als Pivot. btw darf ich das mit der for schleife wegen dem break so handeln ?Warum solltest du das nicht dürfen? Hast du Vorgaben, von denen wir nichts wissen?
Archiv
Dieses Thema wurde archiviert und kann nicht mehr beantwortet werden.