挿入のあるクイックソートソートフィニッシュ - どこが間違っていますか？

Question

私はクラスのプロジェクトに取り組んでいます。指定された値の挿入ソートに移行するクイックソートを記述する必要があります。私が今では難しかった問題は、なぜ私が期待しているパフォーマンスを得ていないのかを理解することです。

要件の1つは、1300ミリ秒未満で5,00,000の整数の配列をソートする必要があることです（これは標準的なマシン上にあるため、CPUの速度は問題になりません）。まず、スタックオーバーフローエラー（再帰呼び出しが多すぎます）のために、5,000,000で動作するようにはできません。私がヒープサイズを大きくすると、私はまだそれよりもかなり遅くなっています。

以下はコードです。誰のヒント？事前に

おかげ

public class MyQuickSort { 

    public static void sort(int [] toSort, int moveToInsertion) 
    { 
     sort(toSort, 0, toSort.length - 1, moveToInsertion); 
    } 

    private static void sort(int[] toSort, int first, int last, int moveToInsertion) 
    { 
     if (first < last) 
     { 
      if ((last - first) < moveToInsertion) 
      { 
       insertionSort(toSort, first, last); 
      } 
      else 
      { 
       int split = quickHelper(toSort, first, last); 
       sort(toSort, first, split - 1, moveToInsertion); 
       sort(toSort, split + 1, last, moveToInsertion); 
      } 
     } 
    } 

    private static int quickHelper(int[] toSort, int first, int last) 
    { 
     sortPivot(toSort, first, last); 
     swap(toSort, first, first + (last - first)/2); 
     int left = first; 
     int right = last; 
     int pivotVal = toSort[first]; 
     do 
     { 
      while ((left < last) && (toSort[left] <= pivotVal)) 
      { 
       left++; 
      } 

      while (toSort[right] > pivotVal) 
      { 
       right--; 
      } 

      if (left < right) 
      { 
       swap(toSort, left, right); 
      } 

     } while (left < right); 

     swap(toSort, first, right); 


     return right; 
    } 

    private static void sortPivot(int[] toSort, int first, int last) 
    { 
     int middle = first + (last - first)/2; 

     if (toSort[middle] < toSort[first]) swap(toSort, first, middle); 

     if (toSort[last] < toSort[middle]) swap(toSort, middle, last); 

     if (toSort[middle] < toSort[first]) swap(toSort, first, middle); 

    } 

    private static void insertionSort(int [] toSort, int first, int last) 
    { 
     for (int nextVal = first + 1; nextVal <= last; nextVal++) 
      { 
       int toInsert = toSort[nextVal]; 
       int j = nextVal - 1; 
       while (j >= 0 && toInsert < toSort[j]) 
       { 
        toSort[j + 1] = toSort[j]; 
        j--; 
       } 
       toSort[j + 1] = toInsert; 
      } 
    } 

    private static void swap(int[] toSort, int i, int j) 
    { 
     int temp = toSort[i]; 
     toSort[i] = toSort[j]; 
     toSort[j] = temp; 
    } 

} 

Answer 1

それを実演しました。

実際には、私の分類はまったく間違っていません。私は0〜100の範囲の数値を生成していました（ソートされているかどうかをテストするため）。その結果、多数の重複が発生し、多くのパーティションに影響を及ぼしていました。範囲をmin_intとmax_intに変更すると、それはずっと速くなりました。

ありがとうございました：D

Answer 2

入力配列は、再帰関数は、スタックオーバーフローの問題に実行することを期待するのは、大規模なその自然です。これは上記のコードを試してみるとここで起こっていることです。独自のスタックを使用してQuicksortを繰り返し書くことをお勧めします。実行時にスタックフレームの割り当て/解放が行われないため、高速にする必要があります。スタックオーバーフローの問題も発生しません。パフォーマンスは、挿入ポイントを実行しているポイントによっても異なります。私は、挿入ソートがクイックソートに比べてひどく実行される特定の入力サイズは持っていません。サイズを変えて試してみることをお勧めします。

パフォーマンスを向上させるために、挿入ソートでバイナリ検索を使用することもできます。私はあなたが小さな入力を実行するときにどれだけ改善するのか分かりませんが、それは素晴らしいトリックです。

再帰クイックソートを反復クイックソートに変換する方法を学ぶことができないため、コードを共有したくありません。反復的なものに変換する際に問題がある場合は、私に知らせてください。

Answer 3

これはあなたのアルゴリズムではテストされていませんが、実行しているデータセットの種類はわかりませんが、左端の要素よりも優れたピボットを選択することを検討してください。クイックソートのウィキペディアから：ピボットの

選択肢クイックソートの非常に初期のバージョン では、 の左端の要素パーティションは、多くの場合、 ピボット要素として選択されます。残念ながら、この は、すでに ソートされた配列で最悪の動作を引き起こします。これはむしろ の一般的な使用例です。この問題は 容易（特により長いパーティションに） 中間パーティションのインデックスまたは を選択し、ピボットのいずれかのため ランダムインデックスを選択することによって解決された パーティションの最初、 中間及び最後の要素の中央値を選択しますピボットのために