Wieso ist das kein InsertionSort?
das ist der Output:
(die erste zeile ist das unsortierte inputarray)
4 Antworten
Der Output entspricht tatsächlich dem von InsertionSort. Es ist aber unnötig umständlich. InsertionSort ist sowieso nicht der schnellste, man muss ihn ja nicht künstlich verlangsamen.
In der inneren Schleife machst du einen unnötigen Dreieckstausch. Du brauchst aber nur einen Wert eine Position weiter zu schieben um Platz zum Einfügen zu machen.
Wenn du die Position zum Einfügen gefunden hast, musst du dort den einzufügenden Wert einfügen (man hat dann gerade dafür Platz gemacht) und die innere Schleife abbrechen. In deiner Version kommen da noch weitere Vergleiche bis zum Index 0 (dia aber alle false ausgehen)
Es gibt auch Versionen, die die Einfügestelle durch binäre Suche finden und dann den entsprechenden Teil in einem Rutsch um eine Position weiterschieben (mit memcopy, das können manche CPUs direkt ausführen)
Lies mal https://de.wikipedia.org/wiki/Insertionsort
und die Anmerkungen zur Implementierung
Hallo.
Die Ausgabe sieht zwar gleich aus, aber deine innere Schleife durchläuft unnötigerweise immer bis zum ersten Element.
Führe mal folgenden Code aus und vergleiche:
import java.util.Arrays;
public class InsertionSort_Differnce {
public static void main(String args[]) {
int[] temp = new int[]{8,7,2,6,1,0,5,7,7};
insertionSort_1(temp);
temp = new int[]{8,7,2,6,1,0,5,7,7};
insertionSort_2(temp);
}
public static void insertionSort_1(int[] arr){
int tmp = arr[0];
int n = 0;
for(int i = 1; i < arr.length; i++) {
n++;
for(int j = i; j > 0; j--) {
n++;
if(arr[j] < arr[j-1]) {
tmp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = tmp;
}
}
System.out.println(Arrays.toString(arr));
}
System.out.println(n + " Durchläufe!\n\n");
}
public static void insertionSort_2(int[] arr){
int n = 0;
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;
n++;
while (j >= 0 && arr[j] > key) {
n++;
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
System.out.println(Arrays.toString(arr));
}
System.out.println(n + " Durchläufe!\n\n");
}
}
Das sieht mir eher nach einem Bubböe Sort aus. Ich glaube beim instertionSort würdest du ein neues Array mit dem kleinsten Element beschreiben. Dann das nächste Suchen usw
aber bei bubble sort wird doch von stufe zu stufe kein sortiertes teilarray gebildet, heir sieht man ja dass die linken teile immer sortiert sind
Bei einem echten "Insertion Sort" müsste die "8" schon beim ersten Vergleich (also in der zweiten Zeile Deiner Ausgabe) ganz hinten landen (bei den gegebenen Zahlen). Das "Insertion" steht ja dafür, dass die Zahl an die korrekte Position "einsortiert" wird und dazu das Array, wenn man denn auf einem Array arbeitet, verschoben werden muss (was dann auch der Hauptaufwand der Methode ist).
achso, dachte ich nehme nur das rechte element vom sortierten array und klatsche es entsprechend in die richtige stelle des sortierten arrays
https://studyflix.de/informatik/insertionsort-1321, aber hier wird komischerweise die 7 nach der 4 belassen, ist das video dann falsch?
Das ist nicht korrekt, wenn ich mich richtig erinnere.
Beim InsertionSort wird tatsächlich, wie der Fragesteller impliziert, das erste Element als sortiert angesehen und die restliche Liste als unsortiert.
Danach wird jedes Element aus der unsortierten Liste entsprechend der passenden Stelle im sortieren Bereich gesetzt.
Also tatsächlich:
[8,7,2,6,1,0,5,7,7]
[7,8,2,6,1,0,5,7,7]
[2,7,8,6,1,0,5,7,7]
[2,6,7,8,1,0,5,7,7]
...
Und so lässt es sich auch bei diesem Video verstehen: