ソートアルゴリズムはH.Cormenの書籍の「Introduction to Algorithms」より速いのはなぜですか？

Question

私は昨日以来この本を勉強しています。最初のアルゴリズムを理解して適用した後、私は自分自身に行き、別の方法で見てみました。ここではJavaの、示されたアルゴリズムでは、です：

public static int[] sort(int[] array) 
{ 
    for(int i = 1; i < array.length; i++){ 
     int value = array[i]; 
     int j = i - 1; 

     while(j >= 0 && array[j] > value){ 
      array[j + 1] = array[j]; 
      j--; 
     } 
     array[j+1] = value; 
    } 

    return array; 
} 

そして、ここでは私のものです：

public static int[] sortb(int[] array) 
{ 
    for(int i = 0; i < array.length; i++){ 
     int value = array[i]; 
     int j = i; 

     while(j < array.length && value > array[j]){ 
      array[j] = array[j + 1]; 
      j++; 
     } 

     array[j] = value; 
    } 

    return array; 
} 

それぞれの関数呼び出しの100万のために、私は2番目のための第1のための32ミリと25ミリ秒を得ました。私はまだアルゴリズムから始まっているので、意味は分かりません。

Answer 1

私はあなたの並べ替えが元のものよりもずっと速い理由を発見しました。あなたは並べ替えを一切していないからです。

あなたのコード

int value = array[i]; 
    int j = i; 

    while(j < array.length && value > array[j]) { ... } 

ためj = iで

、そうvalue == array[j]あなたはwhileループに入る前に、したがって、あなたのwhileループ本体が実行されることはありません。あなたのソート結果は間違っています。それがあなたのコードが非常に高速な主な理由です。

Answer 2

私の経験では（の学生の経験を読んでください）、この種の値はほとんど意味がありません。

多分、もう少しリソースを取ったり解放したりするバックグラウンドプロセスがありました。

あなたが手配しようとした特定のケースが、他のものよりも寓意の1つの方が良いかもしれません。あなたが別のランダムアレイを使用した場合

はたぶん、そのうちの一つは他よりもソートすることが近かった。..

良い対策を持っているために、あなたは通常、1だけでなく、多くのテストをしなければなりません。例えば、言語やコンパイラの時には特定機能、とにかく

.. 10K要素それぞれの1Kアレイを生成し、両方algorythmsとこの配列のそれぞれをソートは、理論的に正確に同じ複雑さとalgorythmsに対して異なる結果を生成することができます（1つの例：C++で気づいたら、2次元配列を最初に列で、次に行で横断すると、逆の場合よりも非常に異なるスピードになりますが、どちらが覚えていないかより速かった。