подсчет количества сравнений в quicksort Дает stackoverflow

Question

Я пытаюсь написать программу, которая подсчитывает количество сравнений в программе быстрой сортировки.

Это мой код

package algo_quicksort; 

public class Algo_quicksort { 

    public static int partition(int[]A,int p,int r){ 
     int x=A[p]; 
     int i=p+1; 
     int temp; 
     for(int j=p+1;j<r;j++){ 
      if(A[j]<x){//if A[j] is bigger than the pivot do nothing 
       temp=A[j]; 
       A[j]=A[i]; 
       A[i]=temp; 
       i++; 
      } 
     } 
     temp=A[p]; 
     A[p]=A[i-1]; 
     A[i-1]=temp; 
     return i-1; 
    } 
    public static long quickSort(int[]A,int startPos,int length){ 
     if(length==1){ 
      return 0; 
     } 
     else{ 
      if(startPos<length){ 
      int pivot= partition(A,0,length); 
      quickSort(A,startPos,pivot+1); 
      quickSort(A, pivot+2,length); 
      return length-startPos-1; 
     } 
      else{ 
       return 0; 
      } 
    } 
    } 


    public static void main(String[] args) { 
     int a[]={3,2,4}; 
     System.out.println("# of comparisons is: " +quickSort(a,0,a.length)); 

     System.out.println("A[] after quicksort is: "); 

     for(int i=0;i<a.length;i++){ 
      System.out.print(a[i]+" "); 
     } 

    } 
} 

она прекрасно работает для любого массива размером 3 или менее, но если это немного больше, чем это дает мне StackOverflow исключение при рекурсивном вызове Я попытался отладки мой код но не мог понять, где это происходит неправильно?

Answer 1

Если у вас есть четыре элемента в массиве, первый проход - 3 сравнения + 2 во втором проходе + 1 в третьем проходе или 6 глубинах. Вы должны подталкивать что-то в стек для каждого сравнения. Это говорит о том, что ваш стек имеет 8 уровней с учетом других подпрограмм вызова кода, однако эти стеки обычно выполняются с указателями стека и могут составлять тысячи записей. JVM Organization объясняет общую структуру.

Answer 2

У вас есть рекурсивная функция, quickSort().

Обычно, когда вы получаете условие stackoverflow с рекурсивными методами, это связано с тем, что вы либо не получаете условие «конец» (или когда останавливаться), либо ваш входной параметр неверен.

Я экспериментировал с вашим кодом, настраивая входной параметр и получив следующий результат.

int a[]={3,2,4,5};  
System.out.println("# of comparisons is: " +quickSort(a,0,a.length -1)); 
//changed from a.length to a.length - 1 

Результат

# сравнений: 2 A [] после сортировки является:

---

Однако я не считаю, что это исправление, потому что если я изменил массив на «int a [] = {5,3,2,4};», то снова возникает ошибка stackoverflow :(

Это заставляет меня поверить, что в вашем конечном состоянии что-то не так ... где-то в quickSort(). Проверьте wikipedia или stackoverflow и проверьте свой код с правильной реализацией.

---

Таким образом, после написания некоторых тестов для этого, кажется, что ваша реализация сортировки неверен. Он возвращает ноль, если длина равна 1. Однако, если я передам ему массив длиной один со значением 5, возвращается ноль, тогда как я бы ожидал. 5.

Это означает, что ваше условие остановки неверно. После некоторых поисковых запросов я обнаружил следующее:

1. Первый = последний; только один элемент в массиве сортируется.
2. Первый> последний; никакие значения в массиве не сортируются.

Тогда вам нужно взглянуть на свои аргументы для quicksort. Я не считаю, что вам нужна начальная позиция или длина массива. Ему просто нужен массив.