I have a base case for my quick sort method but I still get a stack overflow error?

Question

I have a quick sort class that works on smaller list sizes but continuously gets SO errors on larger sizes even though I have a base case. I have a quick sort class that looks like this:

public class QuickSorter extends Sorter
{
  @Override
  public void sort(WordList toSort, Comparator<String> comp) throws NullPointerException{
    // TODO
      int front = 0;
      
      int back = toSort.length() -1;
      
      quickSortRec(toSort, comp, front, back);
      
  }

  private void quickSortRec(WordList list, Comparator<String> comp, int start, int end){
    // TODO
      if (start >= end) {
          return;
      }
    
      int pivotPoint = partition(list, comp, start, end);
         
      quickSortRec(list, comp, start, pivotPoint - 1);
     
      quickSortRec(list, comp, pivotPoint + 1, end);
     
      }
    
  
     
  
         
  

  private int partition(WordList list, Comparator<String> comp, int start, int end){
    // TODO
      String pivotSpot = list.get(end);
      int pivotIndex = start;
     
      for(int i = start; i < end; i++) {
          
          if(comp.compare(list.get(i), pivotSpot) < 0) {
              
              list.swap(i, pivotIndex); 
          }
      }
      
      list.swap(end, pivotIndex);
     
      return pivotIndex;
  
  
  }
}

My code works just fine on smaller lists that I need to sort but I get a repeating StackOverflow exception on line 36

Stack trace looks like this:

Exception in thread "main" java.lang.StackOverflowError
    at hw2.AlphabetComparator.compare(AlphabetComparator.java:1)
    at hw2.Sorter$CountingComparator.compare(Sorter.java:272)
    at hw2.QuickSorter.partition(QuickSorter.java:53)
    at hw2.QuickSorter.quickSortRec(QuickSorter.java:32)
    at hw2.QuickSorter.quickSortRec(QuickSorter.java:36)
    at hw2.QuickSorter.quickSortRec(QuickSorter.java:36)
    at hw2.QuickSorter.quickSortRec(QuickSorter.java:36)
    at hw2.QuickSorter.quickSortRec(QuickSorter.java:36)

AlphabetComparator:

int length = b.length(); // holds smallest length of both strings so I don't get an out of bounds exception with my for loop

      if (a.length() < b.length()) // default length will be String b's length if b is less than a or a and b are ==
      {
          length = a.length();
      }
      for (int i = 0; i < length; i++)
      {
          if (a.charAt(i) != b.charAt(i)) // if character at same index in both strings aren't equal
          {
              if (alphabet.isValid(a.charAt(i)) == true && alphabet.isValid(b.charAt(i)) == true) // if both characters are valid in the alphabet
              {
                  return alphabet.getPosition(a.charAt(i)) - alphabet.getPosition(b.charAt(i)); // return negative or positive
              }
          }
      }
      if (a.length() != b.length())
      {
          if (length == a.length())
          {
              return -1;
          } else
              return 1;
      }
      return 0;
  }
      ```

How are WordList and AlphabetComparator implemented? The problem is happening in the AlphabetComparator.compare method. — AllirionX, Oct 02 '20 at 00:42
@AllirionX I added the alphebetComparator.compare method. I just dont understand why the quick sort works on a list of 10, 100 and 1000 elements but not 10,000 — juicecup, Oct 02 '20 at 01:02

score 2 · Answer 1 · answered Oct 02 '20 at 01:11

You are using recursion to do sorting, and the stack is not infinite. For small (enough) arrays, your recursion stays inside the limit. But for large enough arrays, it blows out the stack. Normally, stack-overflow happens for infinite-loop scenarios, but in your case, you've likely just recursed too deeply due to too wide an array.

ref. https://freecontent.manning.com/stack-safe-recursion-in-java/#:~:text=Default%20stack%20size%20varies%20between,case%20is%20recursive%20method%20calls.

Your next question is likely answered here: How to increase the Java stack size?

I have a base case for my quick sort method but I still get a stack overflow error?

1 Answers1