Quicksort Problematik

[Fanfon]

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.

/* quick.c */

#include <stdio.h>

#define MAX 10

void belegung();

void arraybelegung();

void sortierung (int*, int*);

void druck();

int feld[MAX];

int i;

int hilfe;

int x;

main(void)

{

printf("\n\nQUICKSORT\n");

belegung();

sortierung(feld, feld+MAX-1);

druck();

}

void belegung()

{

for(i=0;i<MAX;i++)

{

feld=MAX-i;

}

printf("\nDie unsortierten Werte lauten: ");

for(i=0;i<MAX;i++)

{

printf("%5d",feld);

}

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;

}

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<MAX;i++)

{

printf("%5d",feld);

}

printf("\n\n");

}

Die Funktionen

void belegung();

void arraybelegung();

void druck();

sind ja egal. Mir geht es um den Algorithmus selbst:

void sortierung (int*, int*);

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;

}

while(++posl <= --posr);

if(links < posr) sortierung(links, posr);

if(posl < rechts) sortierung(posl, rechts);

}

Ich versteh nur noch nicht ganz die Abbruchbedingung der Schleife

while(++posl <= --posr);

bzw.

if(links < posr) sortierung(links, posr);

if(posl < rechts) sortierung(posl, rechts);

Vielleicht könnt ihr mir hierbei helfen!

lg Daniel

[Klotzkopp]

Quicksort beruht darauf, dass ein Feld in zwei Teile zerlegt wird, wobei in dem einen Teil die kleinen und in dem anderne Teil die großen Werte liegen. Dann werden die beiden Teile für sich sortiert.

Ich versteh nur noch nicht ganz die Abbruchbedingung der Schleife

while(++posl <= --posr);

posl und posr laufen aufeinander zu. Wenn sie sich treffen, hast du die Stelle gefunden, wo das Feld für den nächsten Rekursionsschritt geteilt wird. Das ++ und -- bewirkt hier nur, dass die gerade vertauschten Werte nicht noch einmal verglichen werden.

bzw.

if(links < posr) sortierung(links, posr); 

if(posl < rechts) sortierung(posl, rechts);[/code]
Hier passiert die Rekursion. Hier werden die beiden Teile des Feldes für sich sortiert, wenn sie mindestens ein Element enthalten.

[Fanfon]

Danke das kann ich nachvollziehen!

Eine Sache die mir jetzt erst auf gefallen ist.

if(posl > posr)

break;

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?

[Klotzkopp]

Danke das kann ich nachvollziehen!

Eine Sache die mir jetzt erst auf gefallen ist.

if(posl > posr) 

break;[/code]




Das ist noch komisch für mich!Das hat nur den Zweck, die Vertauschung zu verhindern, falls posl und posr schon aneinander vorbeigelaufen sind.



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,
Nein, 6 und 7 werden nicht getauscht, die sind beide größer als 3.



posl läuft von links nach rechts, bis zu einem Wert der >= 3 ist:

[code]while(*posl < x) posl++;

posl bleibt also auf der 7 stehen. posr läuft von rechts nach links, bis zu einem Wert, der <= 3 ist, bleibt also auf der 3 stehen:

7 1 3 5 6

l   r

[/code]


posl und posr sind noch nicht aneinander vorbei, also wird die Schleife hier nicht verlassen, und 3 und 7 werden getauscht:



[code]3 1 7 5 6

l   r

Jetzt wird die Bedingung der äußeren (do/while-)Schleife geprüft, dabei werden posl und posr noch einmal weitergesetzt, sie zeigen dann beide auf die 1.

Hier ist dann wohl ein Fehler im Algorithmus: Bei der Rekursion wird einmal

3 1

und einmal

1 7 5 6

sortiert. Die 1 wird also zu beiden Teilen hinzugenommen.

[Fanfon]

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

Nein, 6 und 7 werden nicht getauscht, die sind beide größer als 3.

posl läuft von links nach rechts, bis zu einem Wert der >= 3 ist:

while(*posl < x) posl++;

posl bleibt also auf der 7 stehen.

gesprochen? Es werden doch in der While-Bedingung nur werte gesucht die explezit größer oder kleiner sind und nicht größer= oder kleiner=?

posl und posr sind noch nicht aneinander vorbei, also wird die Schleife hier nicht verlassen, und 3 und 7 werden getauscht:

Code:

3 1 7 5 6

l   r

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!

Die unsortierten Werte lauten: 7 1 3 10 5 6

Schritt 1:

3 1 7 10 5 6

Schritt 2:

1 3 7 10 5 6

Schritt 3:

1 3 7 5 10 6

Schritt 4:

1 3 5 7 10 6

Die sortierten Werte lauten: 1 3 5 7 10 6

und das Stimmt ja noch nicht!

[Klotzkopp]

Mhmm den Quellcode habe ich mir aus dem Openbook fon C A-Z (Gallileo Computing) abgeleitet.

Bücher enthalten Fehler. Und zu den Büchern von Jürgen Wolf habe ich schon viele negative Kommentare gelesen.

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 Schleife läuft weiter, solange der Wert, auf den posl zeigt, kleiner als x ist. Das heißt, sie bleibt stehen, wenn posl auf einen Wert zeigt, der nicht kleiner als x ist. "Nicht kleiner" ist dasselbe wie "Größer oder gleich".

und das Stimmt ja noch nicht!

Ich gehe davon aus, dass der Algorithmus im Openbook fehlerhaft umgesetzt ist. Das mit MAX ist ja auch falsch.

[Fanfon]

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

[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!