Ich versuche Insertionsort zu verstehen. Ich habe gehört, dass ich es mit einem Wächter verbessern kann.Insertionsort und Sentinels
Dies ist mein Code ohne Sentinel:
public static int[] insertionSort(int[] sortieren) {
int temp;
for (int i = 1; i < sortieren.length; i++) {
temp = sortieren[i];
int j = i;
while (j > 0 && sortieren[j - 1] > temp) {
sortieren[j] = sortieren[j - 1];
j--;
}
sortieren[j] = temp;
}
return sortieren;
}
Ich bin derzeit versucht, in diesem Fall zu verstehen, ich eine ArrayIndexOutOfBounds Exception bekommen kann. Kannst du mir helfen zu verstehen, warum es einen Sentinel gibt, der notwendig ist, um diesen Code zu verbessern, und wo ich ihn eingeben muss? Ich würde sagen, dass ich einen Integer.MIN_Value am linken Rand des Arrays setzen muss, aber ich bin nicht sicher, weil ich keinen Fall sehe, in dem es aus dem Array herausläuft.
Ich würde es schätzen, wenn Sie mir helfen würden, die Verwendung von Sentinels in Insertionsort zu verstehen.
Mit Sentinel ...
public void insertionSort(int[] array) {
int temp;
int arraySentinel[] = new int[array.length+1];
for(int i = 0; i < array.length; i++){
arraySentinel[i+1] = array[i];
}
arraySentinel[0] = Integer.MIN_VALUE;
for (int i = 1; i < arraySentinel.length; i++) {
temp = arraySentinel[i];
int j = i;
/**
* Stabil weil sortieren[j-1] > temp!
* Wäre nicht stabil wenn >=!
*/
while (arraySentinel[j - 1] > temp) {
arraySentinel[j] = arraySentinel[j - 1];
j--;
}
arraySentinel[j] = temp;
}
for (int i = 1; i < arraySentinel.length; i++){
array[i-1] = arraySentinel[i];
}
}
Vielen Dank bis jetzt. Aber wenn ich diesen Sentinel implementieren will, werde ich ein neues Array mit der Länge + 1 haben, ist mein Code dann noch in situ? Oder kann ich das besser umsetzen? Ich habe meinen neuen Code in mein Thema eingefügt. –
Ihre Implementierung scheint korrekt zu sein. Ich kann verstehen, wie es scheint, dass es nicht sinnvoll erscheint, da es für die Gesamtkomplexität keinen Unterschied macht. Aber Sie müssen erkennen, dass Sie nur die Overhead-Konstanten reduzieren und somit die asymptotische Komplexität nicht reduzieren. In der Tat wird Insertion-Sort häufig verwendet, da seine innere Schleife äußerst effizient ist, indem sehr wenige Konstanten verwendet und ausgetauscht werden. –
okay danke. Endlich habe ich das! Vielleicht ist es besser, mit einer ArrayList zu arbeiten. Ich habe den neuen Code hinzugefügt, hoffe, es ist in Ordnung :) –