Fanfon

So habe jetzt das komplette Programm noch mal umgeschrieben, aber den Sortier algorithmus gelassen und es scheint zu funktionieren. #include <stdio.h> void belegung(); void arraybelegung(); void sortierung (int*, int*); void druck(); int feld[1000]; int i; int hilfe; int x; int j=0; int end; main(void) { printf("\n\n====== SORTIERALGORITHMUS 'QUICKSORT' ======\n"); belegung(); sortierung(feld, feld+end-1); druck(); } void belegung() { printf("\nBITTE END-WERT ANGEBEN!\n"); scanf("%d",&end); printf("\nBITTE WERTE EINGEBEN!\n"); for(i=0;i<end;i++) { printf("\nWert %d: ",i+1); scanf("%d",&feld[i]); } printf("\nDIE UNSORTIERTEN WERTE LAUTEN: "); for(i=0;i<end;i++) { printf("%5d",feld[i]); } printf("\n"); } void sortierung(int *links, int *rechts) { int *posl=links; int *posr=rechts; x = *(links + (rechts - links >> 1)); do { while(*posl < x) posl++; while(*posr > x) posr--; if(posl > posr) break; hilfe = *posl; *posl=*posr; *posr=hilfe; printf("\nZWISCHENSCHRITT\n\n"); for(i=0;i<end;i++) { printf("%5d",feld[i]); } printf("\n"); } while(++posl <= --posr); if(links < posr) sortierung(links, posr); if(posl < rechts) sortierung(posl, rechts); } void druck() { printf("\nDIE SORTIERTEN WERTE LAUTEN: "); for(i=0;i<end;i++) { printf("%5d",feld[i]); } printf("\n\n"); } So das wäre das komplette Programm! #include <stdio.h> void belegung(); void arraybelegung(); void sortierung (int*, int*); void druck(); int feld[1000]; int i; int hilfe; int x; int j=0; int end; So Globale Variablendekleration bzw. Initialisierung der Unterfunktionen main(void) { printf("\n\n====== SORTIERALGORITHMUS 'QUICKSORT' ======\n"); belegung(); sortierung(feld, feld+end-1); druck(); } So das Hauptprogramm, welches die einzelnen Hauptfunktionen aufruft! void belegung() { printf("\nBITTE END-WERT ANGEBEN!\n"); scanf("%d",&end); printf("\nBITTE WERTE EINGEBEN!\n"); for(i=0;i<end;i++) { printf("\nWert %d: ",i+1); scanf("%d",&feld[i]); } printf("\nDIE UNSORTIERTEN WERTE LAUTEN: "); for(i=0;i<end;i++) { printf("%5d",feld[i]); } printf("\n"); } So ein Endwert fürs Feld wird abgefragt und in 'end' geschrieben. Einzelnen Werte werden eingegeben und zur Überprüfung ausgegeben. void sortierung(int *links, int *rechts) { int *posl=links; int *posr=rechts; x = *(links + (rechts - links >> 1)); do { while(*posl < x) posl++; while(*posr > x) posr--; if(posl > posr) break; hilfe = *posl; *posl=*posr; *posr=hilfe; printf("\nZWISCHENSCHRITT\n\n"); for(i=0;i<end;i++) { printf("%5d",feld[i]); } printf("\n"); } while(++posl <= --posr); if(links < posr) sortierung(links, posr); if(posl < rechts) sortierung(posl, rechts); } So der Sortieralgorithmus. Übergen wurden der Anfangs wer (0) und der Endwert (end-1) an die Unterfunktion. Ich habe mir die Zwischenschritte mit anzeigen lassen zum besseren Nachvollziehen. Zum Schluss wird eben die Funktion 'sortierung' rekursiv für die Teilstück aufgerufen. void druck() { printf("\nDIE SORTIERTEN WERTE LAUTEN: "); for(i=0;i<end;i++) { printf("%5d",feld[i]); } printf("\n\n"); } Und halt die Ausgabe der sortierten Werte. So im Moment funktioniert es. Die Frage ist ob man den Sortieralgorithmus noch vereinfachen kann oder nicht. Bzw. ob Fehler noch drin sind, falls jemand was auffällt!

Eben das ist ja mein Problem, aber so richtig finde ich den Fehler nicht, weil wenn ich mir den Code von anderen Internetseiten anschaue, dannn sehen die ja eigentlich identisch aus. Eventuell könnte man die Teiler grenzen anders definieren, dass für den Fall, dass die Grenzen gleich sind die rechte grenze um eine Position erhöht wird. oder? dann könnte es ja passieren dass Ein zu kleiner/großer Wert ins falsche Feld gerät. Gibt es eventuell ne gute Internetseite wo man nen richtigen Quellcode bekommt? lg Daniel

Mhmm den Quellcode habe ich mir aus dem Openbook fon C A-Z (Gallileo Computing) abgeleitet. Laut Buch wird feld und feld+max über geben wenn max z.b. zehn ist währe das feld[0] und feld[10] was aber ein max wert (a[10]) ein feldpositions zuviel wäre dann wären wir ja beim 11. element, deswegen habe ich meinen Code als feld und feld+max-1 ausgegeben damit ich auf die ENDTE Position gelange also feld[0] und feld[Max-1]a also feld[10-1] also feld[9] da wo ich auch hin will. So die Abbruch bedingung habe ich verstanden, aber warum wird immer von gesprochen? Es werden doch in der While-Bedingung nur werte gesucht die explezit größer oder kleiner sind und nicht größer= oder kleiner=? Die If Bedingung geht von den Feldpositionen aus. in dem Fall feld[0] >feld[2] Gut verstanden, jetzt ist aber die Frage warum dann zum Schluss trotzdem nicht korrekt ausgeführt wird. Ich habe mir mal die Zwischen Schritte anzeigen lassen! und das Stimmt ja noch nicht!

Danke das kann ich nachvollziehen! Eine Sache die mir jetzt erst auf gefallen ist. Das ist noch komisch für mich! Wenn mann folgendes Beispiel hat! 7 1 3 5 6 und deine 3 ist der Vergleichswert, dann müsste doch 7 und 6 nach dem Algorithmus als erstes getauscht werden, aber vorher wird doch mit dieser IF Anweisung die Schleife abgebrochen und daher findet doch kein Tausch statt oder verstehe ich das falsch?

Hallo, ich bin frisch hier angemeldet da ich ein kleines Problem mit Quicksort habe. Ich soll darüber ein Vortrag halten, bin aber noch nicht ganz sicher mit der Thematik Ich habe die Wikipedia Seiten und diverse andere gelesen und komme auch ganz gut zurecht aber habe noch ein paar Fragen dazu! Ich habe folgendes Programm geschrieben dazu. Die Funktionen void belegung(); void arraybelegung(); void druck(); sind ja egal. Mir geht es um den Algorithmus selbst: void sortierung (int*, int*); Ich versteh nur noch nicht ganz die Abbruchbedingung der Schleife bzw. Vielleicht könnt ihr mir hierbei helfen! lg Daniel