Подсчет сравнений, когда точка не является первым элементом

Question

Я попытался реализовать алгоритм Quicksort, но разные опорные точки, похоже, не работают. Когда элемент поворота не является первым элементом, он всегда заканчивается рекурсивным циклом, что приводит к сбою, когда переменная i падает из массива и снова вызывает себя с полным массивом, и ничего не меняется. Я думаю, что ошибка - это сравнение, сравнивающее сSort [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() не сближаются. Небольшое изменение в последних двух строках будет работать подобно магии.

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 для обновления кода.