InsertionsortとSentinels

Question

私はInsertionsortを理解しようとしています。私はセンチネルで改善できると聞いています。

これはセンチネルのない私のコードです：

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

私はにArrayIndexOutOfBounds例外を取得することができ、その場合に理解することは、現在しようとしています。なぜコードを改善するために必要なSentinelがあるのか​​、どこに入力しなければならないのか理解できるようになりますか？私は配列の左端にInteger.MIN_Valueを置く必要があると言いますが、配列が不足しているケースがないので、わかりません。

私がInsertionsortのセンチネルの使い方を理解するのを助けていただければ幸いです。センチネルで

...

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

静的センチネル、すなわち配列の最初の要素として配置されるであろう非常に低い値となります配列[0]に格納されます。これにより、コード内の条件 "j> 0"をチェックしないという利点があります。

j> 0条件が追加され、プログラムがArrayIndexOutOfBounds Exceptionを与えないようにします。配列[0]にパディング要素を追加し、配列[1 .... n]からループを実行することにより、j> 0条件をチェックするオーバーヘッドを節約します。

無症状でも、挿入ソートの複雑さには影響しません。

編集：修正された実装は正しいです。私はあなたが混乱していると仮定します。今度は、全体の配列をもう一度塗りつぶしなければならないので、それはさらにシータ（n）時間を要します。だからあなたは、センチネルを追加すると実際には遅くなると心配しています。しかし、それはJavaの問題であることを理解する必要があります。 Java配列はサイズが変更できないため、新しい配列を作成する必要がありました。それはアルゴリズムの見通しではありません。アルゴリズムは言語に依存しません。可変サイズの配列を持つ言語やJavaのListを使用する他の言語を使用した場合は、O（1）時間に監視標識を追加することができます。その場合、結果として生じるプログラムはより速くなります。

Answer 2

より大きなサイズの新しいアレイを作る必要はありません。

配列を1つ実行し、最小要素を見つけて0番目の位置に移動します。

この要素はセンチネルとして機能し、境界チェックなしで残りの配列を並べ替えることができます。