Insertionsort und Sentinels

Question

Ich versuche Insertionsort zu verstehen. Ich habe gehört, dass ich es mit einem Wächter verbessern kann.

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]; 
    } 
} 

Answer 1

Eine statische Sentinel einen sehr niedrigen Wert sein wird, der als das erste Element des Feldes platziert wird D.h. im Array [0]. Dies bietet den Vorteil, die Bedingung "j> 0" in Ihrem Code nicht zu überprüfen.

Die Bedingung j> 0 wird hinzugefügt, so dass das Programm keine ArrayIndexOutOfBounds-Ausnahme gibt. Durch das Hinzufügen eines gepolsterten Elements am Array [0] und das Ausführen der Schleife vom Array [1 .... n] sparen wir den Aufwand für die Überprüfung der Bedingung j> 0.

Bitte beachten Sie, dass asymptomatisch, es nirgendwo die Komplexität der Insertion Art beeinflusst.

EDIT: Ihre überarbeitete Implementierung ist korrekt. Ich nehme an, dass du verwirrt bist, weil du jetzt das ganze Array wieder füllen musst, was zusätzliche Theta (n) Zeit benötigt. Sie sind also besorgt, dass Sentinel es tatsächlich langsamer macht. Sie müssen jedoch verstehen, dass das Java-Problem ist. Java-Arrays haben eine unveränderbare Größe und Sie mussten daher ein neues Array erstellen. Das ist nicht der Ausguck des Algorithmus. Algorithmen sind sprachunabhängig. Wenn Sie eine andere Sprache verwendet hätten, die eine veränderbare Größe der Array-Größe oder eine verwendete Java-Liste hat, kann Sentinel in O (1) -Zeit hinzugefügt werden. In diesem Fall wird das resultierende Programm schneller sein.

Answer 2

Sie müssen kein neues Array mit größerer Größe erstellen.

Führen Sie einfach ein Array durch, suchen Sie das minimale Element und verschieben Sie es in die 0. Position.

Jetzt funktioniert dieses Element als Sentinel, und Sie können den Rest des Arrays ohne Grenzprüfung sortieren.