Кто-нибудь знает, почему мой алгоритм быстрой сортировки получает ошибку переполнения стека на больших наборах данных ex. массив длиной 100000?

Question

Мой Java алгоритм быстрой сортировки выдает ошибку переполнения стека для длинных массивов, таких как массив длиной 100 000. Я нахожу свой стержень, используя метод медианы трех. У меня есть мой медиана (медиана) и метод быстрой сортировки (qSortB). Кто-нибудь знает, почему происходит эта ошибка? Спасибо за вашу помощь.

//Finding the pivot using the median of three method
public int median(int low, int high){
    int p;
    int temp;
    int min= list[low];
    //System.out.println("min: "+ min);
    int med=list[(high+low)/2];
    //System.out.println("med: "+ med);
    int max= list[high];
    //System.out.println("max: "+ max);
    if ((min >= med) != (min >= max)) {
      p= min;
    }
  else if ((med >= min) != (med >= max)) {
      p= med;
        temp=list[(high+low)/2];
        list[(high+low)/2] = list[low];
        list[low] =temp;
  }
  else {
      p= max;
      temp=list[high];
        list[high] = list[low];
        list[low] =temp;

  }


    return p;

}

 public void qSortB(int low, int high){
        if(low>=high|| high<=low){
            return;
        }
        else{
            int left=low+1;
            int right=high;
            int pivot =median(low,high);
            //System.out.println("Pivot: "+ pivot);
            int pi=low;
            while(left<=right){
                while(left <len && list[left]< pivot){
                    comp++;
                    left++;
                }
                while(right >-1 && list[right] >pivot){
                    comp++;
                    right--;
                }
                if(left <len && right>-1 && left<=right){
                    comp++;
    //              System.out.println("Swapping "+list[right]
    //                      +" with " + list[left]);

                    int temp=list[left];
                    list[left] = list[right];
                    list[right] = temp;
                    left++;
                    right--;
                    swap++;
                    //print();

                }
                if(left>right){
                    int temp= list[left-1];
                    list[left-1]= pivot;
                    list[pi]= temp;
                    pi=left-1;
                    swap++;
                    qSortB(low,pi-1);
                    qSortB(pi+1,high);
                }
            }   



        }
    }

Answer 1

При передаче большого массива возникает ошибка переполнения стека, поскольку вы должны помнить, где находитесь внутри функции. В qSortB() вы снова вызываете qSortB(), что означает, что вы вызываете другую функцию, не заканчивая предыдущую, потому что вы должны помнить, где находитесь, это занимает больше памяти, пока не вызовет переполнение стека.

Чтобы это исправить, вам не нужно использовать такие большие массивы или переделывать функцию, чтобы использовать al oop вместо того, чтобы вызывать себя таким образом, чтобы функция заканчивалась, предотвращая ошибку переполнения стека.

Как упомянутое fantaghirocco, рекомендую посмотреть эту ссылку