Quicksort algorithm fails on StackOverflow error

Question

I am working on a modified version of Quicksort which uses a formula of ((lowIndex + highIndex) / 2) to decide it's partition.

My code is below. However, whenever I run it, I get the following error:

start ARRAY
1
2
10
9
3
4
8
7
5
6
Exception in thread "main" java.lang.StackOverflowError
        at newQuickSort.quicksort(newQuickSort.java:37)
        at newQuickSort.quicksort(newQuickSort.java:39)

Where the line at newQuickSort.quicksort(newQuickSort.java:39) is repeated.

Essentially, I am simply trying to change the partition function to use median-of-three partitioning, and not really touch the Quicksort algorithm at all, just the Partition function.

I am not exactly sure why this error is occurring, though I have referenced the following:

Any advice would be helpful, thanks!

public class newQuickSort{ 

    static int count;

    static void move(int myArray[], int a, int b){
        int temp;
        temp = myArray[a];
        myArray[a] = myArray[b];
        myArray[b] = temp;
    } //end move

    //Create the partition function
    static int partition(int myArray[], int p, int r){
        int medIndex = (p+r) / 2;
        int pivot;

            if (myArray[p] > myArray[medIndex]){
                move(myArray, p, medIndex); 
            }else if (myArray[p] > myArray[r]){
                move(myArray, p, r);
            }else if (myArray[medIndex] > myArray[r]){
                move(myArray, medIndex, r);
            }
            //end if checks

            //now set proper movements
            move(myArray, medIndex, r-1);
            //set pivot
            pivot = myArray[r-1];
            //return pivot for which to partition around
            return pivot;
    } //end partition 

    static void quicksort(int myArray[], int p, int r){ 
        if (p < r){
        checkCount += 1; 
            int partition = partition(myArray, p, r); 
            quicksort(myArray, p, partition-1); 
            quicksort(myArray, partition+1, r); 
        } //end if 
    } //end quicksort

    public static void main (String[] args){
        int testarray[] = {1,2,10,9,3,4,8,7,5,6};
       // int testarray[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
        System.out.println("start ARRAY");
        for (int i = 0; i < testarray.length; i++){
            System.out.println(testarray[i]);
        } //end for

        int p = 0;
        int r = testarray.length-1;
        newQuickSort mySort = new newQuickSort();
        mySort.quicksort(testarray, p, r);

        System.out.println("end ARRAY");
        for (int j = 0; j < testarray.length; j++){
            System.out.println(testarray[j]);
         } //end for

    }
}

@PM77-1 I was thinking something similar, but I'm not quite sure how to fix that. — artemis, Oct 29 '18 at 20:01
I have been for hours, which is why I am at StackOverflow, hopefully trying to get assistance with a programming question. Per guidelines, please only comment helpful things. Thank you. — artemis, Oct 29 '18 at 20:04
@jerry: imho, suggesting that you do some debugging is a helpful suggestion. To give it more substance, see [How to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) — rici, Oct 29 '18 at 20:16
Hi @rici - I do not think recommending debugging is inherently harmful. I think implying that none has been done is distasteful, when in fact, hours upon hours have already been poured into debugging. I will review that link momentarily. — artemis, Oct 29 '18 at 20:20

rici · Accepted Answer · 2018-10-29T20:10:06.907

1

Your partition function returns the value of the pivot. But its caller (quicksort) is expecting the index of the pivot.

The termination of the recursion depends on the partition point being in the index range.

Once you fix that, consider optimising quicksort to minimise stack usage:

First, recurse to sort the smaller range (in the sense of having fewer elements).
Then loop to to continue with the larger range.

That guarantees that the recursion depth is no more than log₂N.

edited Oct 29 '18 at 20:10

answered Oct 29 '18 at 20:05

rici

234,347
28
237
341

How can I change `pivot = myArray[r-1];` to the index? Remove the myArray[] tag? Thank you for catching that.. I did not notice. – artemis Oct 29 '18 at 20:06
Hi, rici. Thank you for noticing that. When I made the initial change of the partition function, the program now runs with no errors, but does not sort properly. Should I edit my current question, or begin a new one? – artemis Oct 29 '18 at 20:15
@jerry: presumably, the pivot index is `r-1` but you should verify that. – rici Oct 29 '18 at 20:16
@jerry: you shouldn't edit a question into a different question. If you do that, you make the answers useless. – rici Oct 29 '18 at 20:18
thanks for the feedback. I assumed the pivot index was also r-1, but in doing so (by editing the code above), I get a "Finished" array which is unsorted. I can continue to try and play with the logic from here, and then implement your suggestion of calling quicksort on the smaller size first. – artemis Oct 29 '18 at 20:19
By the way, a good debugging technique, as is probably suggested in Eric's blog post, is to check postconditions. Does `partition` partition? That is, when it returns, is the subarray correctly split in two at the pivot point? If not, you know where to look for the problem. – rici Oct 29 '18 at 20:22
understood, thank you very much for your assistance. – artemis Oct 29 '18 at 20:25

Quicksort algorithm fails on StackOverflow error

1 Answers1