# Generic QuickSort causing StackOverflow?

Tags:
1. Apr 15, 2017

### Enharmonics

I have to sort an array in increasing order based on the compareTo method. I'm not allowed to use the Arrays, Collections, Set, or Map classes.

Here's my code:

Code (Java):
public static <T extends Comparable<? super T>>
void sort (T[] arr)
{
// If arr is null, empty,
// or only has 1 element,

if (arr == null || arr.length == 0
|| arr.length == 1)
return;

sort(arr, 0, arr.length - 1);
}

public static <T extends Comparable<? super T>>
void sort(T[] arr, int left, int right)
{

// To be used while sorting

int i = left;
int j = right;

// Check if left and
// right indices are out
// of order. If they are,
// nothing can be done

if (right <= left)
return;

// Middle element used
// as pivot

T pivot = arr[(left + (right - left)) / 2];

// temp will be used
// to swap elements later

T temp;

// QuickSort algorithm

while (i <= j)
{
// Look for values on
// the left greater than
// the pivot and values
// on the right smaller
// than the pivot

// When you find both, swap them

while (arr[i].compareTo(pivot) < 0)
{
i++;
}

while (arr[j].compareTo(pivot) > 0)
{
j--;
}

// Check that i hasn't

if (i <= j)
{

// Swap the items

temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;

// Move both indices
// to their next position

i++;
j--;
}
}

// Recursive calls to the
// sort method

if (left < j)
sort(arr, left, j);
if (i < right)
sort(arr, i, right);
}
The trouble is, I'm getting a StackOverflow error at the line

Code (Java):
while (arr[i].compareTo(pivot) < 0)
And then a whole bunch of them at the line

Code (Java):
sort(arr, i, right);
The fact that I'm getting a bunch of repeated errors at the recursive call line tells me it might be an infinite recursion problem, but I just can't see why.

I also don't know why it's throwing an error at the compareTo line... based on how the method works, it seems like the logic is right? Don't know if it matters, but the array I'm using in my driver to test my QuickSort code is:

Code (Java):
String[] wordArray = {"Droplet", "Blueberry", "Elephant",
"Fate", "Apple", "Coconut", "Darjeeling"};
Any help with this would be appreciated. I'm kinda stumped.

2. Apr 15, 2017

### Borg

You're performing a sort while you are sorting. The compareTo method calls the original sort and that one calls the overloaded version, which then calls itself.

3. Apr 15, 2017

### Enharmonics

I'm a little confused, could you please explain this bit? I thought that (in this case, since the generic type is being replaced by String at compile time) the compareTo method just compared the lengths of the two Strings and returned the difference between them. I checked the Oracle documentation, which says

Why is the sort method being called on the compareTo line? The only thing in the body of the while loop is a statement incrementing the value of i...

4. Apr 15, 2017

### Borg

It looks like it's getting into a state where it's comparing the same value over and over and not incrementing your values like you think.

5. Apr 15, 2017

### Borg

It's hard to tell for sure but it looks like your swap section might get into a state where it keeps flopping the middle value back and forth. In that case, one of the two recursive calls at the bottom will always be called so that it can never get out of the method. Also,based on the pivot declaration, it will only work for odd numbered arrays.

6. Apr 15, 2017

### rcgldr

The issue is the code to choose the pivot value, it should be:

Code (Text):

T pivot = arr[left + (right - left) / 2];

The current code is effectively using T pivot = arr[right / 2], and since right / 2 can be less than left, the pivot value is outside the range left to right. Consider the case where the chosen pivot value is less than all values in the range left to right, the index i will get incremented past right and perhaps past the end of the array, resulting in infinite recursion or segmentation fault.

7. Apr 15, 2017

### Enharmonics

Thank you SO much. That's exactly it.

For some reason I wrote

Code (Text):
T pivot = arr[(left + (right - left)) / 2];
Which, as you said, is mathematically equivalent to arr[right / 2]. I have no idea why I added that extra set of parentheses. Good grief, I gotta watch what I'm doing!