Verständnisproblem InsertionSort.

[NeX]

Hallo!

im Forum gibt es zwar einige Themen zum InsertionSort, aber leider habe ich keine Antwort auf mein (wahrscheinlich dummes) Problem gefunden. Und zwar geht es mir um den InsertionSort, den ich für die Uni verstehen muss.

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

bis zu der while Schleife ist mir klar, was passiert, ich verstehe auch, wie InsertionSort grundsätzlich funktioniert. Die Bedingung für die while-Schleife ist auch noch verständlich, aber dann hört es auf. Ich dachte, dass sich alle Variablen in den eckigen Klammern auf die Werte, und nicht auf den Index beziehen (zum Beispiel key = A[j], für den key 3 in einem Array an der Stelle mit dem Index 2). Aber in der Whileschleife scheint ja mit dem +1 der Index gemeint zu sein.. was passiert da genau?

Gibt es tipps, wie man da den Unterschied leichter sehen kann?
Es wäre super wenn mir das jemand wirklich ganz, ganz simpel erklären könnte!

Liebe Grüße,
NeX

 

[minzee]

Ich bin mir ziemlich sicher, dass der Pseudocode anders ausschaut. Entweder gibt es noch geschwungende Klammern oder od´s. Auf jeden Fall fehlen die Einrückungen, um die Blöcke zu erkennen.

A steht für das Array, also für alle Wert.
int[] A = {10, 20, 30, 40};

A steht für das i´te Element im Array.
int i = 0;
System.out.println(A); // 10

A[i + 1] bedeutet, dass zuerst zu dem i 1 hinzuaddiert wird, und dann dieses Element genommen wird.
int i = 0;
System.out.println(A[i + 1]); // 20

i ist ein Index. A ist ein Element aus dem Array, das über den Index i adressiert wird.

A[i + 1] = A nimmt den Wert beim Index i und kopiert ihn um 1 Stelle nach rechts in das Element mit dem Index i + 1.
int i = 0;
A[i + 1] = A;
System.out.println(A); // 10
System.out.println(A[i + 1]); // 10

Auf diese Weise verschieben sich alle Werte links von i jeweils um 1 Position nach rechts, sofern deren Wert größer sind als der Wert beim Index j.

EDIT: noch einen Schreibfehler korrigiert

 

[NeX]

Hallo!

Vielen Dank für die ausführliche Erklärung, jetzt hab ich's verstanden! War wirklich nur ein total blöder Denkfehler, mit dem Index und dem Wert.

Der Code ist übrigens aus der Vorlesung so übernommen, die Einrückungen hat er mir beim posten anscheinend verschmissen!

Also vielen Dank nochmal, dann kann ich InsertionSort endlich abhaken 🙂

Liebe Grüße,
NeX