2016-05-07 21 views
0

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

Antwort

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.

+0

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. –

+0

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. –

+0

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 :) –

0

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.

+0

haha: D gute Idee danke! ^^ –