How to fix java.lang.StackOverflowError in simple Quicksort without setting array.lenght-1?

user_15575849 0
Viewed 53

Problem: I implemented a quicksort algorithm that unfortunatly just works for some int[] and then breaks. I get the error StackOverflowError

What I tried so far: I have to call the sort(array[], left, right) without the A[r] I cannot modify the sort(array, 0, array.length); to sort(array, 0, array.length-1). My idea was to call a new function that returns length - 1 and attach it to the variable right; It works just for some int[] and then breaks.

My code:

private static class Quicksort {

    private void sort(int[] array, int left, int right) {           
        right = lenRight(array); //to get array.lenght-1
        int l = left;
        int r = right;
        int pivot = array[right];

        // die Partition
        while (l <= r) {
            while (array[l] < pivot)
                l++;
            while (array[r] > pivot)
                r--;

            // die swap
            if (l <= r) {
                int temp = array[l];
                array[l] = array[r];
                array[r] = temp;
                l++; 
                r--;
            }
        }
        if (left < r)
            sort(array, left, r); // where it breaks
        if (right > l)
            sort(array, l, right);
    }

    public int lenRight(int[] array) {
        return array.length - 1;
    }

    public void sort(int[] array) {
        sort(array, 0, array.length);
    }
}

My error

    Testing array [30, 88]
    PASS
    Testing array [75, 35]
    PASS
    Testing array [15, 62]
    PASS
    Testing array [52, 55, 46]
    PASS
    Testing array [18, 22, 56]
    Exception in thread "main" java.lang.StackOverflowError
        at Sorting$Quicksort.sort(Sorting.java:36)
        at Sorting$Quicksort.sort(Sorting.java:36)
        at Sorting$Quicksort.sort(Sorting.java:36)
        at Sorting$Quicksort.sort(Sorting.java:36)
        at Sorting$Quicksort.sort(Sorting.java:36)
        at Sorting$Quicksort.sort(Sorting.java:36)
        at Sorting$Quicksort.sort(Sorting.java:36)
        at Sorting$Quicksort.sort(Sorting.java:36)
        at Sorting$Quicksort.sort(Sorting.java:36)
quicksort arrays java
1 Answers

The code can adjust the right parameter just after entry and when making recursive calls. Should sort be a static function?

    private static void sort(int[] array, int left, int right) { // static?
        right -= 1;                     // adjust
        int l = left;
        int r = right;
        int pivot = array[(l+r)/2];     // middle value better if data already sorted
          while (l <= r) {
            while (array[l] < pivot)
                l++;
            while (array[r] > pivot)
                r--;
            if (l <= r) {
                int temp = array[l];
                array[l] = array[r];
                array[r] = temp;
                l++; 
                r--;
            }
        }
        if (left < r)
            sort(array, left, r+1);     // adjust
        if (l < right)
            sort(array, l, right+1);    // adjust
    }
user_32820560
Related