バブルソートの最適化 - 何が欠けていますか？

Question

バブルソートアルゴリズムの最適化方法を理解しようとしています。より良いソート方法があることは分かっていますが、私は興味があります。

効率をテストするために、私はstd :: chronoを使用しています。プログラムは10000のlong int配列を30回ソートし、平均ソート時間を出力します。数字は、反復ごとにランダムに（最大10000）選択されます。ここにコードはありません。

#include <iostream> 
#include <ctime> 
#include <chrono> 
using namespace std; 



int main() { 


    //bubble sort 
    srand(time(NULL)); 

    chrono::time_point<chrono::steady_clock> start, end; 

    const int n = 10000; 
    int i,j, last, tests = 30,arr[n]; 
    long long total = 0; 
    bool out; 

    while (tests-->0) { 


     for (i = 0; i < n; i++) { 
      arr[i] = rand() % 1000; 
     } 


     j = n; 

     start = chrono::high_resolution_clock::now(); 
     while(1){ 

      out = 0; 
      for (i = 0; i < j - 1; i++) { 

       if (arr[i + 1] < arr[i]) { 
        swap(arr[i + 1], arr[i]); 
        out = 1; 
       } 
      } 

      if (!out) { 
        break; 
      } 

      //j--; 

     } 


     end = chrono::high_resolution_clock::now(); 

     total += chrono::duration_cast<chrono::nanoseconds>(end - start).count(); 
     cout << "Remaining :"<<tests << endl; 

    } 

    cout << "Average :" << total/static_cast<double>(30)/1000000000<<" seconds"; // tests(30) + nanosec -> sec 


    cin.sync(); 
    cin.ignore(); 
    return 0; 
} 

平均ソーティング時間は0.17秒です。

すでにソートされた数値の比較を避けるために47行目（j--;）のコメントを外すと、分かりやすいソート時間が得られます。

スワップが行われた最後の位置を覚えていれば、そのインデックスの後に要素がソートされていることがわかっているので、それ以降の繰り返しでその位置までソートすることができます。このポストの第2部で詳しく説明されています：https://stackoverflow.com/a/16196115/1967496。 これは新しい可能な最適化を実装するコードです：

#include <iostream> 
#include <ctime> 
#include <chrono> 
using namespace std; 



int main() { 


    //bubble sort 
    srand(time(NULL)); 

    chrono::time_point<chrono::steady_clock> start, end; 

    const int n = 10000; 
    int i,j, last, tests = 30,arr[n]; 
    long long total = 0; 
    bool out; 

    while (tests-->0) { 


     for (i = 0; i < n; i++) { 
      arr[i] = rand() % 1000; 
     } 


     j = n; 

     start = chrono::high_resolution_clock::now(); 
     while(1){ 

      out = 0; 
      for (i = 0; i < j - 1; i++) { 

       if (arr[i + 1] < arr[i]) { 
        swap(arr[i + 1], arr[i]); 
        out = 1; 
        last = i; 
       } 
      } 

      if (!out) { 
        break; 
      } 

      j = last + 1; 

     } 


     end = chrono::high_resolution_clock::now(); 

     total += chrono::duration_cast<chrono::nanoseconds>(end - start).count(); 
     cout << "Remaining :"<<tests << endl; 

    } 

    cout << "Average :" << total/static_cast<double>(30)/1000000000<<" seconds"; // tests(30) + nanosec -> sec 


    cin.sync(); 
    cin.ignore(); 
    return 0; 
} 

注ライン40及び48そしてここで問題が来る：平均時間は0.17秒の周りに再びなりました。 私のコードに問題はありますか、何か不足していますか？

更新：

私は今、次の結果の10倍以上の数字でソートして手に入れた： 最適化なし：19.3秒 まず最適化（j--）：14.5秒 セカンド（はず）の最適化を（ j = last + 1）：17.4秒;

私の理解から、2番目の方法はいずれの場合も最初の方法よりも良いはずですが、数値は何か他のことを伝えます。

Answer 1

まあ問題は、この質問に対して正解か間違った答えがないかもしれないということです。

まず、10000要素だけを比較しているときは、それを効率テストと呼ぶことはできません。はるかに高い要素の数を比較してみてください。おそらく500000になるでしょう（しかし、おそらく配列を動力学的に配置する必要があります）。

第2に、それはコンパイラかもしれません。コンパイラは、多くの場合、プログラムの実行がよりスムーズかつ高速に実行されるように、最適化を試みます。