Prozedur SelectionSort

[Tim]

Hey alle zusammen,
ich bin gerade dabei mich auf meine mündliche Informatikprüfung vorzubereiten. Als Thema wurde unter anderem Selectionsort genannt (denke mal, ihr wisst damit was anzufangen :
Das Prinzip hab ich total verstanden und auch die Prinzipielle Umsetzung.
Meine Frage ist jetzt nur:
Welcher Quelltext wäre richtig?
Es geht um folgende drei Zeilen:

Code: Alles auswählen

Temp:=Feld[min];                               	
Feld[min]:=Feld[i];                             	
Feld[i]:=Temp;  

Gehören diese 1) in die 1. For-Schleife 2) in die 2. For-Schleife oder 3) in die IF-Struktur der 2. For-Schleife?
1)

Code: Alles auswählen

Procedure SelectionSort(var Feld :Array of Integer); 	 
	var i, j, Temp, Min: integer;                                       	  
	Begin                                                                          	
		For i:=Low(Feld) to High(Feld) do                 	
		Begin                                                               	
			Min:=i;                                                 	
			For j:=i+1 to High(Feld) do  
         begin                	
				IF Feld[j] < Feld[min] then      	   
					Min:=j;  
         end; 	                       	                    
			Temp:=Feld[min];                               	
			Feld[min]:=Feld[i];                             	
			Feld[i]:=Temp;  				                               
		End;							
	End;	
 

2)

Code: Alles auswählen

Procedure SelectionSort(var Feld :Array of Integer); 	 
	var i, j, Temp, Min: integer;                                       	  
	Begin                                                                          	
		For i:=Low(Feld) to High(Feld) do                 	
		Begin                                                               	
			Min:=i;                                                 	
			For j:=i+1 to High(Feld) do
         begin                 	
				IF Feld[j] < Feld[min] then      	   
					Min:=j;                         	                    
			   Temp:=Feld[min];                               	
			   Feld[min]:=Feld[i];                             	
			   Feld[i]:=Temp; 
         end; 				                               
		End;							
	End;	
 

3)

Code: Alles auswählen

Procedure SelectionSort(var Feld :Array of Integer); 	 
	var i, j, Temp, Min: integer;                                       	  
	Begin                                                                          	
		For i:=Low(Feld) to High(Feld) do                 	
		Begin                                                               	
			Min:=i;                                                 	
			For j:=i+1 to High(Feld) do  
				IF Feld[j] < Feld[min] then
                begin
			               Min:=j;                         	                    
			               Temp:=Feld[min];                               	
			               Feld[min]:=Feld[i];                             	
			               Feld[i]:=Temp;  	
                end;			                               
		End;							
	End;	
 

Und die letzte Frage: Müsste in der 1. For-Schleife (wie in 1.) um die IF-Struktur ein begin/end gesetzt werden oder kann das weggelassen werden, weil die IF-Anweisung als "eine Anweisung" zählt?

Code: Alles auswählen

			For j:=i+1 to High(Feld) do  
         begin                	
				IF Feld[j] < Feld[min] then      	   
					Min:=j;  
         end; 

Code: Alles auswählen

			For j:=i+1 to High(Feld) do             	
				IF Feld[j] < Feld[min] then      	   
					Min:=j;   

Vielen Dank für eure Antworten, ich hoffe ich hab mich verständlich ausgedrückt, wenn nicht einfach nachfragen
Grüße
Tim

[af0815]

Erklär mal was die 3 Zeilen machen, dann wird vielleicht klarer wo die hingehören.

Andreas

[Tim]

Also dann erkläre ich den Algorithmus mal...mit einem Bild:

Ich hoffe, das hilft zum prinzipiellen Verständnis.
Die drei Zeilen dienen dazu, die zu vergleichenden Zahlen zu tauschen, sofern die Zahl an der Stelle j kleiner ist, als an der Stelle i/min.
Dabei wird dann der Index an der Stelle j gleich min gesetzt und der Wert an der Stelle min (j) dann temporär (Temp) gespeichert. Anschließend wird die Zahl an der Stelle i "kopiert" und auf die Stelle min (j) gesetzt.
Damit die Zahlen jetzt getauscht sind wird das Array an der Stelle i gleich dem Wert von Temp gesetzt.

Hoffe es half

Grüße
TIm

[wp_xyz]

Ich glaube, Andreas weiß schon, wie der Selection Sort funktioniert, ich denke, er wollte dich motivieren, über den Algorithmus nachzudenken. Deine gezeigten Routinen enthalten zwei for-Schleifen. Die äußere Schleife durchläuft dein Array von vorne bis hinten. Die Elemente vor dem äußeren Index (i) sind sortiert, die folgenden sind unsortiert. In der inneren Schleife wird das Minimum der unsortierten Elemente gesucht und durch Vertauschen ans Ende des sortierten Bereichs gesetzt. Die Vertauschung wird durch die von dir angefragten drei Zeilen vorgenommen. Was passiert, wenn die Vertauschung außerhalb (Code 1) oder innerhalb (Code 2 und 3) der inneren Schleife erfolgt? An welcher Stelle in den drei Code-Beispielen kennt man das Minimum?

Mehr Tipps gebe ich nicht, es ist immerhin deine Prüfung...

Zur Frage mit dem begin/end: Die IF-Anweisung wird wie eine einzige Anweisung gezählt, selbst wenn nach ein ELSE-Zweig folgt, und wenn hinter dem THEN/ELSE ein weiterer BEGIN/END-Block steht, auch wenn sich alles über viele Zeilen erstreckt. Daher ist die zweite Form der FOR-Schleife durchaus richtig, weil hier nach dem FOR nur eine einzige Anweisung, nämlich das IF, folgt. Viele Leute bevorzugen aber die erste Schreibweise, weil man beim Programmieren oft die Situation hat, dass man in die Schleife noch weitere Anweisungen aufnehmen muss. Und dann ist es gut, wenn das begin/end schon da steht, dann kann man's nicht mehr vergessen. Aber das ist Geschmackssache. Am wichtigsten ist immer, den Code sauber einzurücken, so dass man die Block-Struktur mit einem Blick erkennt - das machst du übrigens sehr gut (im Gegensatz zu manch anderen Beispielen, die ich hier schon gesehen habe).

[Tim]

Ah, ich glaub ich habs verstanden! Du hast mir das nochmal ganz anders erklärt, als ich es gedacht hatte. Ich bin nämlich davon ausgegangen, dass sobald der Wert an der Stelle j kleiner ist, als an der Stelle i, getauscht wird.
Aber dem scheint ja gar nicht so zu sein, denn wie du gesagt hast, wird gleich mit der 2. For-Schleife das minimum im Unsortierten Bereich gesucht und erst wenn die 2. For-Schleife das Array durchlaufen hat, wird die Stelle mit dem Minimum mit dem Wert an i getauscht!
Dementsprechend glaube ich, dass Variante 1 richtig ist!

So hat es uns auch unsere Lehrerin gegeben (aber einfach nur an die Tafel geschmissen und nichts erklärt), nur kann ich nach den zwei Jahren Unterricht bei ihr leider nicht darauf vertrauen, dass ein Quelltext richtig ist...wie oft kam es vor dass sie ein Schüler (meist ich ) sie korrigieren musste, weil ihr Programm nicht funktioniert hat! Deshalb habe ich mir halt selber noch mal Gedanken darüber gemacht, bin aber eher daran verzweifelt...

Gut, okay, das mit der IF-Anweisung hab ich auch verstanden - man könnte also in Variante 1) das begin und end auch weglassen.
Ich werde mir das nochmal als Text aufschreiben, wie der Algorithmus zu erklären ist, denn es fällt mir ziemlich schwer das mit den ganzen Schleifen und min, i, j und so in Worte zu fassen.

Vielen, vielen Dank für eure Hilfe! Ist gut, wenn man eine Anlaufstelle hat, wenn man mal was nicht so verstanden hat!

Viele Grüße
TIm