Generic QuickSort causing StackOverflow?

[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:

public static <T extends Comparable<? super T>>
    void sort (T[] arr)
    {
        // If arr is null, empty,
        // or only has 1 element,
        // it is already sorted
       
        if (arr == null || arr.length == 0
                || arr.length == 1)
            return;
       
        // Call overloaded sort method
       
        sort(arr, 0, arr.length - 1);
    }

    // OVERLOADED SORT METHOD
   
    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
            // passed j already
           
            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

while (arr[i].compareTo(pivot) < 0)

And then a whole bunch of them at the line

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:

String[] wordArray = {"Droplet", "Blueberry", "Elephant",
                "Fate", "Apple", "Coconut", "Darjeeling"};

Any help with this would be appreciated. I'm kinda stumped.

 

[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.

 

[Enharmonics]

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.

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

public int compareTo(String anotherString)

This is the definition of lexicographic ordering. If two strings are different, then either they have different characters at some index that is a valid index for both strings, or their lengths are different, or both. If they have different characters at one or more index positions, let k be the smallest such index; then the string whose character at position k has the smaller value, as determined by using the < operator, lexicographically precedes the other string. In this case, compareTo returns the difference of the two character values at position k in the two string -- that is, the value:

this.charAt(k)-anotherString.charAt(k)

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...

 

[Borg]

Sorry, I misstated about the compareTo method. I thought that you were overloading the compareTo method.

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.

 

[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.

 

[rcgldr]

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

        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.

 

[Enharmonics]

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

        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.

Thank you SO much. That's exactly it.

For some reason I wrote

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 got to watch what I'm doing!