quicksort algorithmus
-
huhu,ich habe die aufgabe gestellt bekommen einen sortieralgorithmus zu erstellen.
Es sollen zahlen mit ziffern aus einem festen intervall genommen werden.mein ansatz war erstmal mit festen zahlen zu arbeiten die in einem array gespeichert sind.danach wollte ich das ganze ausweiten.jemand ne ahnung wie ich die bedingung anders stellen muss,damit er richtig sortiert?also prob iss,dass wenn ich 2 gleiche zahlen drin habe,sortiert er nicht ganz richtig.habe erstmal 6 schritte angegeben in der letzten for schleife.
/ #include<stdio.h> #include<stdlib.h> #include<time.h> void swap (int *px, int *py) { int speicher; speicher = *px; *px = *py; *py = speicher; } long int cmp (int *pA, int *pB, int a, int b) { int pivot, *x; printf("*pA = %d", *pA);printf("\n*pB = %d", *pB); while (pA != pB && pA < pB) /* tue dies solange, bis InhaltpA = Inhaltpb ODER AdressepA größer als AdressepB*/ { pivot = (a+b)/2; printf("\npivot = %d", pivot); if (pivot < 1 || pivot > 6) { printf("pivotfalsch"); break;} while (*pA < pivot && *pA != pivot) /*tue dies solange, bis InhaltpA größer als pivot ODER InhaltpA = pivot*/ /*die beiden Suchzeiger verschieben*/ { *pA++; printf("\n*pA = %d", *pA);; }printf("\n*pA = %d", *pA); while (*pB > pivot && *pB != pivot) /*tue dies solange, bis InhaltpB kleiner als pivot ODER InhaltpB = pivot*/ { *pB--; printf("\n*pB = %d", *pB); }printf("\n*pB = %d", *pB); if (*pA > *pB || pA != pB) /*falls InhaltpA (= untererSuchzeiger) größer als InhaltpB (=obererSuchzeiger)*/ { printf("--->swap! *pA = %d , *pB = %d\n", *pA, *pB); swap(pA,pB); } } /*pB in suche1 ist falsch*/ printf("break\n"); /*neueGrenzen*/ x = pB; /*Adresse von der Mitte zurückgeben*/ return x; } int main(void) { int A[6]; const int Unt_Grenze = 1, Ob_Grenze = 6; /*bei Zufallszahlen: a = Unt_Grenze, b = Ob_Grenze */ int a = Unt_Grenze - 1; /*a & b = Indizes!*/ int b = Ob_Grenze - 1; int i, Ob_Grenze_neu , Unt_Grenze_neu, *p_neueGrenze, *p_neueGrenze1, *p_neueGrenze2,j; int *pMainA, *pMainB; A[0] = 1; A[1] = 5; A[2] = 4; A[3] = 3; A[4] = 4; A[5] = 1; for (i = 0; i < 6; i++) printf("A[%d] = %d\n", i, A[i]); pMainA = &A[a]; pMainB = &A[b]; p_neueGrenze = cmp(pMainA,pMainB,Unt_Grenze,Ob_Grenze); /*1-Mal ausführen, um IntervallMitte zu bekommen*/ printf("\nInhalt neueGrenze = %d Adresse neue Grenze = %d\n", *p_neueGrenze, p_neueGrenze); Unt_Grenze_neu = Ob_Grenze_neu = *p_neueGrenze; p_neueGrenze2 = p_neueGrenze1 = p_neueGrenze; for (i = 0; i < 6; i++) printf("\nA[%d] = %d", i, A[i]); for (j =0; j<4; j++) { printf("\nInhalt neueGrenze1 = %d Adresse neue Grenze1 = %d\n", *p_neueGrenze1, p_neueGrenze1); p_neueGrenze1 = cmp(pMainA, p_neueGrenze1, Unt_Grenze, Ob_Grenze_neu); /*unteres Intervall pMainB Falsch*/ Ob_Grenze_neu = *p_neueGrenze1; printf("\nInhalt neueGrenze2 = %d Adresse neue Grenze2 = %d\n", *p_neueGrenze2, p_neueGrenze2); p_neueGrenze2 = cmp(p_neueGrenze2, pMainB, Unt_Grenze_neu+1, Ob_Grenze); /*oberes Intervall*/ Unt_Grenze_neu = *p_neueGrenze2; for (i = 0; i < 6; i++) printf("\nA[%d] = %d", i, A[i]); } /*while (Unt_Grenze_neu != Ob_Grenze_neu);*/ /* for (i = 0; i < 6; i++) printf("\nA[%d] = %d", i, A[i]);*/ return 0; }
-
falsches forum, das ist offenbar reines C
-
Also irgendwie passen deine Schleifenbedingungen nicht ganz, könnte es daran liegen?
ph1l schrieb:
while (pA != pB && pA < pB) /* tue dies solange, bis InhaltpA = Inhaltpb ODER AdressepA größer als AdressepB*/Du vergleichst hier zweimal die Adressen, richtig sollte sein:
while(*pA!=*pB && pA<pB)while (*pA < pivot && *pA != pivot) /*tue dies solange, bis InhaltpA größer als pivot ODER InhaltpA = pivot*/Nicht ganz so gravierend - aber die zweite Bedingung ist überflüssig
-
huhu thx für die antworten,habe das ganze nochmal anders geschrieben,jedoch stürzt er irgendwie immer ab,weil er die endlosschleife nicht verlässt.
#include<stdio.h> #include<stdlib.h> #include<time.h> void swap (int *px, int *py) /* vertausche Zeiger px mit Zeiger py */ { int speicher; speicher = *px; *px = *py; *py = speicher; }/* swap */ void cmp (int *pA, int a, int b) { int pivot; int links = pA[a]; int rechts = pA[b]; pivot = pA[(a+b)/2]; printf("\npivot = %d", pivot); if (a != b && b != 0 && a != 9) { for (;;) { if (a >= b) break; /*solange ausführen, bis sich Indizes überschneiden*/ if (links > pivot && rechts < pivot) { printf("p[a-1],p[b+1] = %d , %d", pA[a-1],pA[b+1]); swap(&pA[a-1], &pA[b+1]); printf("--->swap! links = %d , rechts = %d\n", links, rechts); } links = pA[a++]; /*Zeiger verschieben*/ printf("\nlinks = %d", links); rechts = pA[b--]; /*Zeiger verschieben*/ printf("\nrechts = %d", rechts); printf ("\na,b = %d,%d\n",a,b); getchar(); } } cmp(pA,0,b); cmp(pA,a,9); printf("break\n"); /*neueGrenzen*/ }/* cmp */ int main(void) { int A[10]; int a = 0; /*a & b = Indizes!*/ int b = 9; int l = 1; /* l & k = Grenzen der Zufallszahlen*/ int k = 100; int i, j; /*Zählvariablen*/ int *pMainA; int InhaltA; /* l = untere Intervallgrenze, k = obere Intervallgrenze */ time_t tim; time(&tim); srand((unsigned int)tim); for (i = 0; i < 10; i++) { /* Array mit Zufallszahlen im Intervall [l,k] erzeugen*/ A[i] = rand() % (k + 1 - l) + l; InhaltA = A[i]; printf("\n A[%d] = %d", i, InhaltA); } pMainA = &A[0]; /* pMainA = Zeiger auf A */ // for (j = 0; j < 10; j++) cmp(pMainA,a,b); for (i = 0; i < 10; i++) printf("\nA[%d] = %d", i, A[i]); return 0; }
-
Ich glaube, du solltest nochmal einen Schritt zurück gehen und dir den Quicksort-Algorithmus genauer ansehen (eine Google-Suche könnte da weiterhelfen).
Was auf jeden Fall merkwürdig aussieht, sind die Grenzen für die rekursiven Funktionsaufrufe.