QuickSort von Pointer array auf Struct

[Dionysos211]

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

[Hexagon]

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.

[Dionysos211]

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 2011 von Dionysos211

[Hexagon]

Hm... okay, das wäre ein hilfreicher Zusatz gewessen, aber kann es auch sein das strcmp char Zeiger will und keine char Arrays?

[Dionysos211]

?

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

[Klotzkopp]

das funktioniert auch alles nur muss ich mir jetzt quasi ein my_quicksort() basteln...

Dann zeig doch mal, was du bis jetzt hast.

[Dionysos211]

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

[Dionysos211]

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 2011 von Dionysos211

[Klotzkopp]

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?