Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Generic QuickSort causing StackOverflow?

  1. Apr 15, 2017 #1
    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,
            // 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

    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. jcsd
  3. Apr 15, 2017 #2

    Borg

    User Avatar
    Science Advisor
    Gold Member

    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.
     
  4. Apr 15, 2017 #3
    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...
     
  5. Apr 15, 2017 #4

    Borg

    User Avatar
    Science Advisor
    Gold Member

    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.
     
  6. Apr 15, 2017 #5

    Borg

    User Avatar
    Science Advisor
    Gold Member

    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.
     
  7. Apr 15, 2017 #6

    rcgldr

    User Avatar
    Homework Helper

    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.
     
  8. Apr 15, 2017 #7
    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!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Generic QuickSort causing StackOverflow?
  1. Quicksort comparison (Replies: 1)

Loading...