java.lang.IllegalArgumentException in QuickSort method

Question

I am following the following pseudocode:

function quicksort(array)
    if length(array) > 1
        pivot := select any element of array
        left := first index of array
        right := last index of array
        while left ≤ right
            while array[left] < pivot
                left := left + 1
            while array[right] > pivot
                right := right - 1
            if left ≤ right
                swap array[left] with array[right]
                left := left + 1
                right := right - 1
        quicksort(array from first index to right)
        quicksort(array from left to last index)

but when I try to implement it in java, I insert code:

import java.util.Arrays;

public class ALGQuickSort {

public static void main(String[] args) {
    int[] array = {6, 3, 4, 8, 9, 10, 1};
    quickSort(array);
    System.out.println(Arrays.toString(array));
}

public static void quickSort(int[] array) {
    int pivot = array[array.length - 1];
    if (array.length > 1) {
        int left = 0;
        int right = array.length - 1;
        while (left <= right) {
            while (array[left] < pivot) {
                left++;
            }
            while (array[right] > pivot) {
                right--;
            }
            if (left <= right) {
                swap(array[left], array[right]);
                right--;
                left++;
            }
            int[] array1 = Arrays.copyOfRange(array, 0, right);
            int[] array2 = Arrays.copyOfRange(array, left, array.length - 1);
            quickSort(array1);
            quickSort(array2);

        }
    }

}

public static void swap(int a, int b) {
    int aux = a;
    a = b;
    b = aux;
}

}

the system shows me the following error on the screen:

Exception in thread "main" java.lang.IllegalArgumentException: 5 > 4 at java.util.Arrays.copyOfRange(Arrays.java:3591) at alg.quicksort.ALGQuickSort.quickSort(ALGQuickSort.java:43) at alg.quicksort.ALGQuickSort.quickSort(ALGQuickSort.java:44) at alg.quicksort.ALGQuickSort.main(ALGQuickSort.java:21) C:\Users\Alex\AppData\Local\NetBeans\Cache\8.2\executor-snippets\run.xml:53: Java returned: 1

the error is in the line:

int[] array2 = Arrays.copyOfRange(array, left, array.length - 1);

someone can help me pls?

Answer 1

Improvements/corrections to your quick-sort algorithm:

1. Correct your swap method: The swap method that you are using will not work.
2. The recursive call should be outside the for loop: Your pseudo-code is correct, but in your implementation it is not the case.
3. Place the Pivot at its correct position and then have a recursive call on sub-arrays that now (for-sure) should not contain the pivot element. After the while loop, you are sure that right+1 == left (think on it a bit and you will understand why this is true). Now swap the array[left] with pivot element and give a recursive call on 2 different sub-arrays (left sub-array to the pivot is beginIndex..right and right sub-array to the pivot is left+1..endIndex where I assume that you need to sort array[beginIndex..endIndex])
4. Avoid copying: Its better to avoid copying a part of the array (instead you can pass the startIndex and the endIndex to denote the sub-array you want to sort)
5. Use Randomized Quick sort: It would also be better if you don't always select the last element as your pivot (what you can do here is just before starting to sort select any random element and then swap it with the last element of your array. Using this strategy you don't have to make much changes in your existing code) This selection of random element as pivot is much better. See this link for more details.
6. Make swap method private: Not relevant to the algorithm, but it is good if you make the swap method private as you might not intend to call it from outside of this class.

If you intend to swap the elements of array with index say index1 and index2, then the following code will work:

public static void swap(int[] array, int index1, int index2) {
    int aux = array[index1];
    array[index1] = array[index2];
    array[index2] = aux;
}

The following is the final code with all the above suggested changes:

public static void main(String[] args) {
    int[] array = {6, 30, 7, 23, 4, 8, 9, 10, 1, 90};
    quickSort(array, 0, array.length - 1);
    System.out.println(Arrays.toString(array));
}

public static void quickSort(int[] array, int beginIndex, int endIndex) {
    // System.out.println("called quick sort on the following : " + beginIndex + " " + endIndex);
    int arrayLength = endIndex - beginIndex + 1;
    int pivot = array[endIndex];
    if (arrayLength > 1) {
        int left = beginIndex;
        int right = endIndex - 1;
        while (left <= right) {
            // System.out.println(left + " " + right);
            while (left <= endIndex && array[left] < pivot) {
                left++;
            }
            while (right >= beginIndex && array[right] > pivot) {
                right--;
            }
            if (left <= right) {
                swap(array, left, right);
                right--;
                left++;
            }

        }
        swap(array, left, endIndex); // this is crucial, and you missed it
        if (beginIndex < right) {
            quickSort(array, beginIndex, right);
        }
        if (left + 1 < endIndex) {
            quickSort(array, left + 1, endIndex);
        }
    }

}

private static void swap(int[] array, int index1, int index2) {
    int aux = array[index1];
    array[index1] = array[index2];
    array[index2] = aux;
}