Javaクイックソート二次ランタイム動作

Question

Javaで効率的なソートアルゴリズムを実装しようとしました。このような理由から、私はまた、クイックソートを実装し、次のコードを使用します。

public class Sorting { 
    private static Random prng; 

    private static Random getPrng() { 
     if (prng == null) { 
      prng = new Random(); 
     } 
     return prng; 
    } 

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

    public static void sortInternal(int[] array, int start, int end) { 
     if (end - start < 50) { 
      insertionSortInternal(array, start, end); 
     } else { 
      quickSortInternal(array, start, end); 
     } 
    } 

    private static void insertionSortInternal(int[] array, int start, int end) { 
     for (int i=start; i<end - 1; ++i) { 
      for (int ptr=i; ptr>0 && array[ptr - 1] < array[ptr]; ptr--) { 
       ArrayUtilities.swap(array, ptr, ptr - 1); 
      } 
     } 
    } 

    private static void quickSortInternal(int[] array, int start, int end) { 
     int pivotPos = getPrng().nextInt(end - start); 
     int pivot = array[start + pivotPos]; 
     ArrayUtilities.swap(array, start + pivotPos, end - 1); 
     int left = start; 
     int right = end - 2; 
     while (left < right) { 
      while (array[left] <= pivot && left < right) { 
       ++left; 
      } 
      if (left == right) break; 
      while (array[right] >= pivot && left < right) { 
       right--; 
      } 
      if (left == right) break; 
      ArrayUtilities.swap(array, left, right); 
     } 
     ArrayUtilities.swap(array, left, end - 1); 
     sortInternal(array, start, left); 
     sortInternal(array, left + 1, end); 
    } 
} 

ArrayUtilities.swapだけで、アレイ内の与えられた二つの要素を交換します。このコードから、私はO(n log(n))実行時の動作を期待しています。

10000要素：32ms

20000要素：128ms

30000の要素：試験は、それぞれの場合に100回を実行296ms

しかし、ソートする配列のいくつかの異なる長さは、以下の結果を与えました次に、実行時間の算術平均を計算した。しかし、予想される動作とは対照的に、ランタイムはO(n^2)です。私のアルゴリズムに何が問題なのですか？

Answer 1

あなたの挿入ソートの実装では、配列は降順でソートされますが、クイックソートでは配列は昇順でソートされます。だから、（降順のために）置き換える：あなたのインデックスが正しくないよう

for (int ptr=i; ptr>0 && array[ptr - 1] < array[ptr]; ptr--) 

for (int ptr=i; ptr>0 && array[ptr - 1] > array[ptr]; ptr--) 

でまたようです。 交換してみてください。

sortInternal(array, 0, array.length - 1); 

で：

sortInternal(array, 0, array.length); 

および挿入でソート最初のループのためにあなたがend - 1をする必要はありません、すなわち使用：

最後に

for (int i=start; i<end; ++i) 

、クイックソート方法の先頭にif (start >= end) return;を追加します。

と述べた@ljeabmreosnとして、50は少し大きすぎる、私は役立ちますことを願っています

5〜20何かを選択しているだろう！

Answer 2

長さが50未満の配列の挿入ソートを持つ「最適化された」QuickSortが問題になっているようです。

私が65の配列を持っていて、ピボットがその配列のメジアンになったとします。あなたのコードを通して配列を実行した場合、あなたのコードはピボットの左右にある2つの32の長さのサブ配列にInsertion Sortを使用します。これは、〜O（2 *（n/2）^ 2 + n）=〜O（n^2）平均の場合に帰着する。クイックソートを使用し、最初のピボットにa pivot picking strategyを実装すると、時間平均の場合は〜O（（n log（n））+ n）=〜O（n（log（n）+1））=〜O n * log（n））である。挿入配列は、配列がほぼソートされている場合にのみ使用されるため、使用しないでください。並べ替えの実際の実行時間のためにのみ挿入並べ替えを使用している場合は、標準のクイックソートアルゴリズム（深い再帰）よりも速く実行される可能性がありますが、Insertion Sortより速く実行される非再帰的クイックソートアルゴリズムを常に利用できます。

「50」を「20」に変更し、結果を観察することがあります。