Why is my quickSort method giving me a StackOverflowError? Java

Question

Here is my quickSort method. It consists of two separate methods: one that takes a queue as a parameter (1), and one that takes an array as a parameter (2). Then it uses the parameter array to make the queue to be passed to (1).

(2)

public static <E> void quickSort(
   E[] array,
   Comparator<E> comp,
   long start,
   long timeOut
) throws TimeoutException {
   Queue<E> queue = new LinkedQueue<>();

   for (int i = 0; i < array.length; i++)
   {
      queue.enqueue(array[i]);
   }

   quickSort(queue, comp, start, timeOut);

   Object[] newArray =  new Object[queue.size()];

   for ( int i = 0; i < queue.size(); i++)
   {
      newArray[i] = queue.dequeue();
   }

   if (System.currentTimeMillis() - start > timeOut)
   {
      throw new TimeoutException("Quick sort has timed out.");
   }       
}

(1)

public static <E> void quickSort(
   Queue<E> queue,
   Comparator<E> comp,
   long start,
   long timeOut
) throws TimeoutException {
   if (System.currentTimeMillis() - start > timeOut)
   {
      throw new TimeoutException("Quick sort has timed out.");
   }

   int n = queue.size();
   if (n < 2)
   {
      return;
   }

   // divide
   E pivot = queue.first();

   Queue<E> L = new LinkedQueue<>();
   Queue<E> E = new LinkedQueue<>();
   Queue<E> G = new LinkedQueue<>();

   while (!queue.isEmpty())
   {
      E element = queue.dequeue();
      int c = comp.compare(element, pivot);

      if (c < 0)
      {
         L.enqueue(element);
      }
      else if (c == 0)
      {
         E.enqueue(element);
      }
      else
      {
         G.enqueue(element);
      }
   }

   // conquer
   quickSort(L,comp,start,timeOut);
   quickSort(G,comp,start,timeOut);

   // concatenate results

   while (!L.isEmpty())
   {
      queue.enqueue(L.dequeue());
   }

   while(!E.isEmpty())
   {
      queue.enqueue(E.dequeue());
   }

   while(!G.isEmpty())
   {
      queue.enqueue(G.dequeue());
   }       
}

LinkedQueue Class:

import java.io.File;

public class LinkedQueue<E> implements Queue<E> {
    private SinglyLinkedList<E> list = new SinglyLinkedList<>();
    public LinkedQueue(){}
    public int size(){return list.size();}
    public boolean isEmpty(){return list.isEmpty();}
    public void enqueue(E element){list.addLast(element);}
    public E first(){return list.first();}
    public E dequeue(){return list.removeFirst();}
}

NameComparator:

public class NameComparator implements Comparator<Employee> {    
    public int compare(Employee a, Employee b)
    {
        String nameA = a.getName();
        String nameB = b.getName();
        int returnValue = 0;
        returnValue = nameA.compareTo(nameB);
        if (returnValue == 0)
        {
            return returnValue;
        }
        else if(returnValue == 1)
        {
            returnValue = -1;
            return returnValue;
        }
        else
        {
            returnValue = 1;
            return returnValue;
        }

    }
}

Output:

run:
Time to create unsorted array : 0 ms
Time to copy unsorted array : 0 ms
fvuvdm,xezvdfqvom,oqqoj,azhjksqjt,tburnf,mkyroq,yokgqrfsiz,mrexmktnz,dqbey,uvbipqag,
Exception in thread "main" java.lang.StackOverflowError
    at LinkedQueue.dequeue(LinkedQueue.java:29)
    at Sort.quickSort(Sort.java:256)
    at Sort.quickSort(Sort.java:276)
    at Sort.quickSort(Sort.java:276)
    at Sort.quickSort(Sort.java:276)
    at Sort.quickSort(Sort.java:276)
    at Sort.quickSort(Sort.java:276)
    at Sort.quickSort(Sort.java:276)
//this continues for many lines

C:\Users\jackm\AppData\Local\NetBeans\Cache\11.0\executor-snippets\run.xml:111: The following error occurred while executing this line:
C:\Users\jackm\AppData\Local\NetBeans\Cache\11.0\executor-snippets\run.xml:94: Java returned: 1
BUILD FAILED (total time: 0 seconds)

I can't figure out why this is happening.

Answer 1

I think that your problem is in your comparator.

Consider this expression:

"dog".compareTo("and")

It will return 3. But your comparator is only testing for 0 and 1. It will go into the else case, when I think you really want it to take the returnValue == 1 case.

Since your comparator returns 1 most of the time, most of the items you pull off your queue will wind up going into G, and the number of nested calls to quickSort will be about the same as the length of your input array. (Note that in your stack trace, most of the calls to quickSort are from the same line, which is probably the one that sorts G.) So if the number of items in your array is large, that could produce the StackOverflowError you are seeing.

It looks like you want your comparator to reverse the sort order of the strings. You should just use:

return -a.getName().compareTo(b.getName())

or

return b.getName().compareTo(a.getName())