Bubble-Sort

TrappedUnderIce

Hallo,

wir haben in der Vorlesung folgende Variante von Bubble-Sort besprochen:

void bubbleSort(RecTyp liste[], int S[])
{
	int i, m, change;
	do
	{
		change=0;
		for(i=1; i<=n-1; i++)
		{
			if(liste[S[i]].SAttr > liste[S[i+1]].SAttr)
			{
				m=S[i]; S[i]=S[i+1]; S[i+1]=m;
				change=1;
			}
		}

	}
	while(change)

}

Wieso wird ein Array auch nochmals durchlaufen wenn die letzte Vergleichsoperation keinen Tausch zur Folge hatte (change wird doch dann 0 gesetzt und die Schleife bricht ab) bzw. sehe ich gerade überhaupt nicht wieso ein Array nochmals von vorne durchlaufen werden sollte?

Vielen Dank für eure Hilfe!

SeppJ

TrappedUnderIce schrieb:

Wieso wird ein Array auch nochmals durchlaufen wenn die letzte Vergleichsoperation keinen Tausch zur Folge hatte (change wird doch dann 0 gesetzt und die Schleife bricht ab)

Es wird doch nur dann noch einmal durchlaufen, wenn irgendeine Vergleichsoperation (Also auch die letzte. Was sollte an der letzten besonders sein?) einen Tausch zur Folge hatte, eben weil change bei jeder Vertauschung auf 1 gesetzt wird und ohne Vertauschungaktion 0 bleibt.

bzw. sehe ich gerade überhaupt nicht wieso ein Array nochmals von vorne durchlaufen werden sollte?

Weil es sonst nicht sortiert ist?

Entweder verstehe ich deine Fragen nicht richtig oder du hast den Code falsch verstanden und stellst deswegen unpassende Fragen. Dir ist schon klar, dass die innere Schleife (Zeilen 7-12) über das ganze Array geht und die äußere Schleife (4-15) so lange solche Volldurchläufe durchführt, bis das Feld sortiert ist (was dadurch festgestellt wird, dass im letzten Durchlauf keine Vertauschungen mehr stattfanden)?

edit: Zu viele doppelte Verneinungen verwirren nicht nur den Leser, sondern auch mich selbst. Nun sollte der Beitrag lesbar (und sogar richtig!) sein.

TrappedUnderIce

[quote="SeppJ"]

TrappedUnderIce schrieb:

Entweder verstehe ich deine Fragen nicht richtig oder du hast den Code falsch verstanden und stellst deswegen unpassende Fragen. Dir ist schon klar, dass die innere Schleife (Zeilen 7-12) über das ganze Array geht und die äußere Schleife (4-15) so lange solche Volldurchläufe durchführt, bis das Feld sortiert ist (was dadurch festgestellt wird, dass im letzten Durchlauf keine Vertauschungen mehr stattfanden)?

ich fürchte das ist der Fall.

Die äußere Schleife wird doch nur ausgeführt solange change=1 ist?!
Irgendwie hab ich mich da in etwas verrannt...

SeppJ

TrappedUnderIce schrieb:

Die äußere Schleife wird doch nur ausgeführt solange change=1 ist?!

Ja. Und da vor dem Beginn der inneren Schleife^* change = 0 gesetzt wird und dann in der inneren Schleife nur dann change auf 1 gesetzt wird, wenn eine Vertauschung statt findet, hört die äußere Schleife genau dann auf, wenn in der inneren Schleife keine Vertauschung stattgefunden hat.

^*: Vor dem Beginn der gesamtem inneren Schleife wohlgemerkt. Nicht bei jedem einzelnen Durchlauf der inneren Schleife.

osdt

Zeile 11 wird unabhängig von der Bedingung immer ausgeführt. Du hast zwar korrekt eingerückt, aber ...

BTW: das erste Element eines Arrays hat den index 0.

SeppJ

osdt schrieb:

Zeile 11 wird unabhängig von der Bedingung immer ausgeführt. Du hast zwar korrekt eingerückt, aber ...

Das habe ich gar nicht gesehen. Somit sind natürlich das Programm selbst und sämtliche Antworten meinerseits komplett falsch. Aber ich vermute mal, dass das im Originalprogramm gar nicht so ist, sondern ein Tippfehler seitens des Threaderstellers. Wenn das im Original richtig gemacht ist, dann ist natürlich auch meine Erklärung wieder richtig .

TrappedUnderIce

Ich habe es jetzt entsprechend korrigiert und denke dass ich den Code jetzt verstanden hab. Sobald bei der inneren Schleife change bei einem beliebigen Schleifendurchlauf auf 1 gesetzt wird, wird ja die äußere Schleife nach Durchlauf der Inneren erneut ausgeführt.

Danke an alle Helfer!