InsertionSort sortiert erste Zahl im Array nicht mit?

[NeX]

Hallo!

Ich habe mich an InsertionSort versucht, und irgendwie sortiert er mir zwar mein Array, aber die erste Zahl ist immer unsortiert - bin den Code jetzt tausend mal durchgegangen und finde den Fehler einfach nicht 🙁

public class InsertionSort2 {

	public static void main(String[] args) {
		
		
	int A [] = {5, 4, 2, 7, 6};
	
	for(int m = 0; m < A.length; m++){
		System.out.println(A[m]);
		}
	
	int key;
	int i;
	
		for(int j = 1; j < A.length; j++){
			key = A[j];
			i = j - 1;
		
			while(i > 0 & A[i] > key){
				A[i + 1] = A[i];
				i = i -1;
			}
			
			A[i+1] = key;
			
		}
		

		for(int k = 0; k < A.length; k++){
			System.out.print(A[k]);
		}
		

		
	}

}

Wäre super wenn mir jemand einen Tipp geben könnte!

Liebe Grüße,
NeX

 

[Joose]

		for(int j = 1; j < A.length; j++){
			key = A[j];
			i = j - 1;
		
			while(i > 0 & A[i] > key){
				A[i + 1] = A[i];
				i = i -1;
			}
			A[i+1] = key;
		}

In Java beginnen Arrays mit Index 0
In der Bedingung der while-Schleife muss i größer 0 sein. Somit kannst du nie die Zahl an Index 0 ändern

 

[NeX]

Ja, das macht Sinn..
aber wie kann ich das dann ändern? Wenn ich auf sobald es gleich oder größer gleich 0 ist, erhalte ich ja eine IndexOutOfBounds Exception 🙁

 

[Joose]

Vergleiche deine Implementierung von Insertionsort doch mit der Pseudocode Variante von Wikipedia: Insertionsort
Ich glaube du hast da ein paar kleiner Fehler drinnen 😉

 

[NeX]

Ich habe mich nach dem Pseudocode aus unserer Vorlesung gerichtet, dem hier:

InsertionSort(array of int A)
for j = 2 to A.length do
     key = A[j ]
     i = j - 1
     while i > 0 and A[i ] > key do
          A[i + 1] = A[i]
          i = i + 1
A[i + 1] = key

aber werd's jetzt wohl mal anders probieren, aber verstehen würde ich es halt schon gerne :/

 

[Joose]

Ja der Pseudocode der Vorlesung ist meiner Meinung nach falsch 😉
Damit kann nie auf Index 0 zugegriffen werden.

Außerdem hast du beim Implementieren des Pseudocode aus der Vorlesung einen kleinen Vorzeichen Fehler 😉 in der while-Schleife sollte i um 1 erhöht werden, du reduzierst i um 1.

aber verstehen würde ich es halt schon gerne :/

Stift + Papier und einen Schreibtischtest durchführen 🙂 damit sollte dir klar werden was warum passiert

 

[Tassimmo]

Ich weiß nicht, ob Fremdlinks erlaubt sind; aber ich hab die ganzen Sortierungsverfahren an der Uni mit folgendem Video recht gut verstanden:
https://www.youtube.com/watch?v=ROalU379l3U
Zu genial 😉