クイックソート/挿入クイックソートだけのコンボスピードより遅い？

Question

Quicksortを10回実行し、平均平均時間を取得します。 私はQicksort/Insertionソートの組み合わせで同じことをしていますが、クイックソートよりも遅いようです。

は、ここで私は挿入ソート

public static <T extends Comparable<? super T>> void OptQSort2 (T[] data, int min, int max) { 
     int indexofpartition; 
     if(max - min > 0) { 
      if((max - min) <= 10) { 
       // Use InsertionSort now 
       InsertionSort.sort(data); 
       return; 
      } else { 
       indexofpartition = findPartition(data, min, max); 

       OptQSort2(data, min, indexofpartition - 1); 

       OptQSort2(data, indexofpartition + 1, max); 
      } 
     } 

} 

と定期的なクイックソートは、ちょうど上記のスニペットと同じである呼び出すコードの一部だが、挿入ソートを呼び出す場合の条件なし。次のように

FindPartitionは次のとおりです。

public static <T extends Comparable<? super T>> int findPartition(T[] data, int min, int max) { 
    int left, right; 
    T temp, partitionelement; 
    int middle = (min + max)/2; 

    partitionelement = data[middle]; 
    left = min; 
    right = max; 

    while(left < right) { 
     while(data[left].compareTo(partitionelement) <= 0 && left < right) 
      left++; 

     while(data[right].compareTo(partitionelement) > 0) 
      right--; 

     if(left < right) { 
      temp = data[left]; 
      data[left] = data[right]; 
      data[right] = temp; 
     } 
    } 

（挿入ソートを使用しています）だけクイックソートとOptSort2の平均時間は

Sorted using QuickSort in: 3858841 
Sorted using OptQSort2 in: 34359610 

任意のアイデアなぜですか？シーケンスのサイズは重要ですか？私はこのために1000要素のInteger []配列を使用しています

Answer 1

は、小さなパーティションについて、次の関数呼び出しがあります。

InsertionSort.sort(data); 

を、これは小さなパーティションを並べ替えるの挿入することになっていますか？あなたが挿入全体の配列のをソートしているようです。 minとmaxのインデックスをInsertionSortに渡すべきではありませんか？

もう1つの方法は、OptQSort2の間に小さいパーティションでは作業を行わないことです。次に、OptQSort2が作業を完了した後で、アレイ全体を単一のInsertionSortのパスで実行します。

Answer 2

テストにはもっと大きな整数配列が必要です。この時点で、おそらくif条件をテストすると、QS + ISの場合にアルゴリズムが遅くなる可能性があります。

大量のデータをテストし、データのサイズがL1キャッシュに収まるのに十分な場合、つまり32-64kbの場合はISに切り替えます。

Answer 3

最初の疑わしいのは、明らかにあなたの挿入方法です。それは本当に例を並べ替えますか？

さらに、JVMをウォームアップするためには、10回以上テストする必要があります。また、両方の注文でそれらをテストするので、一方が他方によって実行されるウォームアップの恩恵を受けることはありません。私は100または1000のテストをお勧めします。そしてそれらはすべて同じデータセットになければなりません。 OptQSort2で

Answer 4

サブアレイの要素が10個以下になるたびに、InsertionSortを呼び出すことは避けてください。

public static <T extends Comparable<? super T>> void OptQSort2 (T[] data, int min, int max) { 
    int indexofpartition; 
     if((max - min) > 10) { 
      indexofpartition = findPartition(data, min, max); 

      OptQSort2(data, min, indexofpartition - 1); 

      OptQSort2(data, indexofpartition + 1, max); 
     } 

} 

完了したら、配列全体に対してInsertionSortを呼び出します。