Ошибка реализации массива программ Quicksort без сортировки сгенерированных чисел

Question

Я новичок в программировании и, похоже, не могу понять свои ошибки при попытке написать программу Quicksort. Я выполнил большую часть реализации, за исключением нескольких ошибок, которые я не могу понять. Вот мой текущий код:

public class Quicksort {
    public static void main(String[] args) {

        Integer[] numbers = new Integer[20];
        for (int i = 0; i < numbers.length; i++) {
            numbers[i] = (int) (Math.random() * 100);
        }


        printArray(numbers);


        quicksort(numbers);


        printArray(numbers);
    }


    public static <T> void printArray(T[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + (i < array.length - 1 ? ", " : "\n"));
        }
    }


    public static <T> void printArrayPartition(T[] array, int low, int high, int pivot) {
        for (int i = 0; i < array.length; i++) {
            String element = "" + array[i];
            if (i == pivot)
                element = "*" + element + "*";
            if (i == low)
                element = "[" + element;
            if (i == high)
                element += "]";
            System.out.print(element + (i < array.length - 1 ? ", " : "\n"));
        }
    }

    public static <T extends Comparable<T>> void quicksort(T[] array) {
        quicksort(array, 0, array.length - 1);
    }

    private static <T extends Comparable<T>> void quicksort(T[] array, int low, int high) {

        if (low < high) {
            int pivotIndex = partition(array, low, high);
            int pivot = pivotIndex;

            printArrayPartition(array, low, high, pivot);

            quicksort(array, low - 1, pivotIndex - 1);
            quicksort(array, pivotIndex + 1, high + 1);
        }
    }

    private static <T extends Comparable<T>> int partition(T[] array, int low, int high) {

        T pivotValue = array[high];

        int left = low;


        for (int i = 0; i < array.length; i++) {

            if (array[i].compareTo(pivotValue) > 0) {

                left++;
            }
        }

        swap(array, high, left);

        return left;
    }

    private static <T> void swap(T[] array, int a, int b) {
        T temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
}

При запуске этой программы я получаю ошибку ArrayIndexOutOfBounds и не знаю почему. Я несколько раз отследил свой код и до сих пор не могу понять это.

Трассировка стека:

54, 91, 26, 43, 98, 65, 88, 78, 88, 60, 58, 75, 74, 46, 79, 81, 64, 49, 67, 31
[54, 91, 26, 43, 98, 65, 88, 78, 88, 60, 58, 75, 74, 46, 79, 81, 64, 49, *31*, 67]
54, 91, 26, 43, 98, 65, 88, 78, 88, 60, 58, 75, 74, 46, *49*, 81, 64, 79], 31, 67
54, 91, 26, 43, 98, 65, 88, 78, 88, 60, 58, 75, 74, 49], *46*, 81, 64, 79, 31, 67
54, 91, 26, 43, 98, 65, 88, 78, 88, 60, 58, 75, *49*, 74], 46, 81, 64, 79, 31, 67
54, 91, 26, *75*, 98, 65, 88, 78, 88, 60, 58, 43], 49, 74, 46, 81, 64, 79, 31, 67
54, 91, 46], 75, 98, 65, 88, 78, 88, 60, 58, 43, 49, 74, *26*, 81, 64, 79, 31, 67
54, 91, *74*, 75, 98, 65, 88, 78, 88, 60, 58, 43, 49, 46], 26, 81, 64, 79, 31, 67
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -6
    at Quicksort.swap(Quicksort.java:79)
    at Quicksort.partition(Quicksort.java:72)
    at Quicksort.quicksort(Quicksort.java:47)
    at Quicksort.quicksort(Quicksort.java:52)
    at Quicksort.quicksort(Quicksort.java:52)
    at Quicksort.quicksort(Quicksort.java:52)
    at Quicksort.quicksort(Quicksort.java:52)
    at Quicksort.quicksort(Quicksort.java:52)
    at Quicksort.quicksort(Quicksort.java:52)
    at Quicksort.quicksort(Quicksort.java:52)
    at Quicksort.quicksort(Quicksort.java:41)
    at Quicksort.main(Quicksort.java:13)

Answer 1

В ваших рекурсивных вызовах:

quicksort(array, low - 1, pivotIndex - 1);
quicksort(array, pivotIndex + 1, high + 1);

Вы вычитаете одно из low и pivotIndex, а затем передаете эти значения в

swap(array, high, left);  //via int left = low;

Который в свою очередь вызывает индексы high и low. При запуске метод low устанавливается на ноль. И затем вы вычитаете один, чтобы получить отрицательное число. Если условие: if (array[i].compareTo(pivotValue) > 0) никогда не выполняется, то left никогда не будет увеличено, и вы передадите отрицательное число на swap(…). А в методе swap():

T temp = array[a];   //a is left here
    array[a] = array[b];
    array[b] = temp;

Вы напрямую пытаетесь вызвать индекс left, который может быть отрицательным числом, то есть indexoutofboundsexception с отрицательным индексом

И таким же образом quicksort(array, pivotIndex + 1, high + 1); может добавить один к high и, таким образом, заставить его выйти за границы