Javaクイックソートピボット選択

Question

ピボットをさまざまな方法で選択すると、着信arraylistの最後の要素以外のものを選択するときにスタックオーバーフローエラーが発生しました。 「中央値3」の選択では、それが最も起こっている場所です。

public static <T> void quickSort (ArrayList<T> incomingArray, Comparator<? super T> cmp, int start, int end) 
{ 
    if(start >= end) 
     return; 

    T pivot = incomingArray.get(start + ((end - start)/2)); <--Stack overflow 

    if(cmp.compare(incomingArray.get(start + ((end - start)/2)), incomingArray.get(0)) < 0) 
    { 
     swap(incomingArray, (start + ((end - start)/2)), 0); 
    } 
    if(cmp.compare(incomingArray.get(end), incomingArray.get(start + ((end - start)/2))) < 0) 
    { 
     swap(incomingArray, end, (start + ((end - start)/2))); 
    } 
    if(cmp.compare(incomingArray.get((start + ((end - start)/2))), incomingArray.get(end)) < 0) 
    { 
     swap(incomingArray, 0, end); 
    } 

    swap(incomingArray, (start + ((end - start)/2)), end); 

    pivot = incomingArray.get(end); 

    int leftBound = 0; 
    int rightBound = end - 1; 

    while(leftBound < rightBound) 
    { 
     while(cmp.compare(incomingArray.get(leftBound), pivot) <= 0 && leftBound < rightBound) 
      leftBound++; 
     while(cmp.compare(incomingArray.get(rightBound), pivot) >= 0 && leftBound < rightBound) 
      rightBound--; 

     swap(incomingArray, leftBound, rightBound); 
    } 

    swap(incomingArray, rightBound, end); 

    quickSort(incomingArray, cmp, start, leftBound); 
    quickSort(incomingArray, cmp, rightBound + 1, end); 



} 

スワップコールは、渡された配列内のインデックス位置の値を変更するだけです。

Answer 1

OKではないようですまず最初：

if(cmp.compare(incomingArray.get((start + ((end - start)/2))), incomingArray.get(end)) < 0) 
{ 
    swap(incomingArray, 0, end); 
} 

は、スタックオーバーフローが原因である可能性があります真ん中と最後の要素を比較したが、結果

Answer 2

として最初と最後の要素を交換あなたのクイックソートの実装でエラーになります。私があなたのコードを正しく理解していれば、私はいくつかの奇妙な行を見つけます。 quicksort(start, end)は、次の行は、あまり意味がありません包括的インデックスendへのインデックスstartから部分配列をソートすると仮定すると

：

if (cmp.compare(incomingArray.get(start + ((end - start)/2)), incomingArray.get(0)) < 0) { 
    swap(incomingArray, (start + ((end - start)/2)), 0); 
} 

ここ

インデックス0は、ほとんどの時間はにstartの外にある場に出ますend。ライン

swap(incomingArray, 0, end); 

と

int leftBound = 0; 

あなたのアルゴリズムの問​​題を修正して再試行してくださいと同じ。

Answer 3

私はちょうどあなたのコードを貼り付けてコピーし、100,000の数字のためにそれを走らせました。スワップと比較機能が期待通りに正しく動作していますか？