-1

My Java quick sort algorithm is throwing a stack overflow error on arrays that are long such as an array of length 100,000. I am finding my pivot using the median of three method. I have my median(median) and quick sort method(qSortB) enclosed. Does anyone know why this error is occurring? Thank you for you help. 

//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);
                }
            }   



        }
    }
Aaron T
  • 1
  • When you make a function call (recursive or not) you use a bit of stack space. I guess, you have too many recursive calls to `qSortB()`. – 001 Feb 11 '20 at 14:09
  • Does this answer your question? [What is a StackOverflowError?](https://stackoverflow.com/questions/214741/what-is-a-stackoverflowerror) – fantaghirocco Feb 11 '20 at 14:13
  • The code is trying to modify Hoare partition scheme to put the pivot in place, which isn't how Hoare partition scheme normally works. Take a look at the [wiki example](https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme). Median of 3 should just compare and swap, in pseudocode: `| md = lo+(hi-lo)/2 | if(a[lo] > a[hi]) swap(a[lo], a[hi]) | if(a[lo] > a[md]) swap(a[lo], a[md]) | if(a[md] > a[hi]) swap(a[md], a[hi]) | ` . Using the wiki scheme, the pivot must not be at a[hi], and the median of 3 as shown in this comment will not cause that to happen. – rcgldr Feb 11 '20 at 20:54

1 Answers1

-1

You have a stack overflow error, when you pass in a large array since you must remember where you are inside the function. In qSortB() you are calling qSortB() again, which means you call another function, while not ending your previous one because you must remember where you are, this takes up more memory until it causes the stack to overflow.

To fix this, you need to not use such large arrays, or rework the function to use a loop instead of calling itself, that way the function will end, preventing the stack overflow error.

As fantaghirocco mentioned, I recommend looking at this link

tyhdefu
  • 90
  • 7