ピボットが最初の要素でないときのカウント比較

Question

私はクイックソートアルゴリズムを実装しようとしましたが、異なるピボットは機能していないようです。 ピボット要素が最初の要素でない場合、常に循環ループで終了し、変数iが配列から外れ、完全配列で再び呼び出され、何も変更されません。私は、エラーは、ピボット値、または他の要素と交換された後の最初の要素と[[j]を比較して比較していると思う。

public static void quickSort(int[] toSort, int l, int r){ 
    if(r - l <= 1)return; 
    counter += r - l - 1; 
    int p = choosePivot(l, r); 
    int pivot = toSort[p]; 
    int oldP = toSort[p]; 
    toSort[p] = toSort[l]; 
    toSort[l] = oldP; 

    int i = l + 1; 
    for(int j = l + 1; j < r; j++){ 
     if(toSort[j] < pivot){ 
      int swap = toSort[j]; 
      toSort[j] = toSort[i]; 
      toSort[i] = swap; 
      i++; 
     } 
    } 


    oldP = toSort[i - 1]; 
    toSort[i - 1] = toSort[l]; 
    toSort[l] = oldP; 

    quickSort(toSort, l, i); 
    quickSort(toSort, i, r); 
} 

public static int choosePivot(int m, int n){ 
    return n - 1; 
    //return m; 
} 

Answer 1

quickSort()への再帰呼び出しが収束しないという問題があります。最後の2行のわずかな変更は魔法のように機能します。

public static void quickSort(int[] toSort, int l, int r){ 
    if(r - l <= 1)return; 
    counter += r - l - 1; 
    int p = choosePivot(l, r); 
    int pivot = toSort[p]; 
    int oldP = toSort[p]; 
    toSort[p] = toSort[l]; 
    toSort[l] = oldP; 

    int i = l + 1; 
    for(int j = l + 1; j < r; j++){ 
     if(toSort[j] < pivot){ 
      int swap = toSort[j]; 
      toSort[j] = toSort[i]; 
      toSort[i] = swap; 
      i++; 
     } 
    } 


    oldP = toSort[i - 1]; 
    toSort[i - 1] = toSort[l]; 
    toSort[l] = oldP; 

    quickSort(toSort, l, i-1); 
    quickSort(toSort, i, r); 
} 

public static int choosePivot(int m, int n){ 
    return n - 1; 
    //return m; 
} 

あなたは、更新されたコードのためのIdeone linkを確認することができます。