Insertion- und Selectionsort

Hallöle,

ich beschäftige mich mit Sortieralgorithmen und habe nun so einige, auch anspruchsvollere wie Quicksort verstanden und mit Java umsetzen können.
Nun stehe ich ganz schön auf dem Schlauch, was zwei viel einfachere Algorithmen angeht.
Ich habe auf einer Webseite vor längerer Zeit (habe leider den Link nicht mehr finden können…) eine Umsetzung dazu gesehen, für Insertionsort und dazu auch gleich die passende Erweiterung für Shellsort.

Nun stehe ich vollkommen auf dem Schlauch, weil ich nicht so ganz nachvollziehen kann, wie das arbeitet. Ich weiß, wie beide Algorithmen in der Theorie funktionieren, kann aber die spezifischen Algorithmen an dieser Stelle nicht so ganz nachvollziehen.

zu Insertionsort:

		
        for(int i=1; i<numbers.length; i++) {
        	int temp = numbers**;
        	int j = i;
            while(j>0 && numbers[j-1]>temp) {
            	numbers[j] = numbers[j-1];
                j--;
            }
            numbers[j] = temp;
        }```

Und dann Shellsort:
```int[] numbers = {19, -14, 11, -18, -1, 5, 14, 6, -2, 17, 13, -17, 15, 10, 7, 12, -7, -16, -19, -8, 8, 4, 16, -10, 9, -11, 20, -6, 1, -20, 3, 0, -13, 18, -4, -3, -9, -12, 2, -15, -5};
		
        int[] cols = {1391376, 463792, 198768, 86961, 33936, 13776, 4592, 1968, 861, 336, 112, 48, 21, 7, 3, 1};

        for(int k=0; k<cols.length; k++) {
            int h = cols[k];
            for(int i=h; i<numbers.length; i++) {
                int j = i;
                int temp = numbers[j];
                while(j>=h && numbers[j-h]>temp) {
                	numbers[j] = numbers[j-h];
                    j -= h;
                }
                numbers[j] = temp;
            }
        }```

Könnte mir einer von euch bitte erläutern, wie der Insertionsortalgorithmus da oben versucht zu arbeiten?
Ich denke, dass ich dann auch den passenden Shellsort dazu verstehen werde.

Ich danke euch im Voraus.

Schöne Grüße und einen tollen Samstag
Gruß
FranzFerdinand

[quote=FranzFerdinand]Könnte mir einer von euch bitte erläutern, wie der Insertionsortalgorithmus da oben versucht zu arbeiten?[/quote]Das ist doch ziemlich klar zu sehen:

[ul]
[li]Die äußere for Schleife gibt einen Index in der Liste vor (i).[/li][li]Der Wert an diesem Index wird in temp gespeichert.[/li][li]Ausgehend von diesem Index verschiebt das while alle Vorgänger (j-1), die größer als der Wert in temp sind um eins nach hinten.[/li][li]wenn der Wert des Vorgängers (j-1) nicht größer als temp ist muss temp dessen Nachfolger (j) werden, weil ja alle Einträge mit Index > j größer als temp sind.[/li] [li] wenn die richtige Stelle für temp gefunden wurde geht’s mit dem nächsten i weiter.[/li][/ul]

Aber wer den Code nicht versteht, für den ist des Beschreibung wenig hilfreich.
Lass es uns also man durchspielen:

i=1, temp= -14

j=1, numbers[j-1(0)]=19
19>-14  ->  numbers[j(1)] <-  19

j=0 -> numbers[j(0)]=19 wegen Sonderbedingung...
[HR][/HR]
i=2 temp= 11
j=2, numbers[j-1(1)]=19
19 > 11 ->  numbers[j(2)] <-  19

j=1 numbers[j-1(0)]= -14
-14 < 11 -> numbers[j(1)] <-  11
[HR][/HR]
i=3 temp= -18
j=3, numbers[j-1(2)]=19
19 > -18 -> numbers[j(3)] <-  19

j=2, numbers[j-1(1)]=11
11 > -18 -> numbers[j(2)] <-  11

j=1, numbers[j-1(0)]=-14
-14 > -18 -> numbers[j(1)] <-  -14

j=0,-> numbers[j(0)]=-18 wegen Sonderbedingung...

usw...

Das Entscheidende ist: vor dem while sind alle Werte vor Index i bereits sortiert und das while muss dann nur den richtigen Platz für den aktuellen Wert in dem sortierten Teil finden.

bye
TT

Hallo Timothy_Truckle,

ich danke Dir vielmals für Deine Antwort. Ich stand echt nur ein wenig auf dem Schlauch. Ich sehe schon anhand Deiner Erklärung da oben, was meine “Gedankenbremse” war.
Das mit dem Verschieben der Vorgänger nach hinten, um temp richtig zu positionieren hab ich echt nicht so recht gesehen. Nun scheint es eindeutig. Shellsort ergibt sich dann auch von selbst. Ich hab den Shellsort noch ein bisschen angepasst, damit er bis auf die “cols” identisch mit dem Insertionsort ist. Das ist nun auch verständlich.

Vielen Lieben Dank dafür.

Schöne Grüße
Lukas