Невозможно вызвать метод сортировки в моей реализации быстрой сортировки

Question

Я пытаюсь закодировать алгоритм быстрой сортировки с использованием Java.Моя проблема в том, что я не могу вызвать метод sort.Это мой код:

public class quickSort
{

int  partition(int a[], int left, int right)
{
    int i= left, j= right, temp;
    int pivot=a[j];
    //System.out.println(pivot+"pivot");
    while(i<=j)
    {
        while(a[i]<pivot)
            i++;
        while(a[j-1]>pivot)
            j++;

        if(i<j)
        {
            temp=a[i];
            a[i]=a[j-1];
            a[j-1]=temp;
            System.out.println(a[i] +"i");
            System.out.println(a[j-1] +"j");
            i++;
            j--;
        }
    }
    System.out.println(i);
    System.out.println(j);
    return i;
}
int[] sort(int[] numbers, int left, int right)
{
    int x = partition(numbers, left, right);
    System.out.println(x +"Qi");
    if(left < right)
        sort(numbers, left, x-1);
        sort(numbers, x+1, right);
    return numbers; 
}


public static void main(String[] args)
    {
    quickSort q= new quickSort();

    int[] numbers = {2,6,4,9,7,0,1,3,5}; 
    int left = 0, right=numbers.length-1;
    q.sort(numbers, left, right);
    }
}

проблема:

sort(numbers, left, x-1);
sort(numbers, x+1, right); 

эта рекурсия не выполняется

Это также приводит к исключению вне границ, когда я пытаюськодировать в методе разбиения.

Это снимок экрана с выводом, который я использую, просто чтобы отобразить вывод и показать IDE, которую я использовал для выполнения: https://drive.google.com/file/d/1j6lHuEONZkO_Dr3ZszoPKh4bNXZgkgbT/view?usp=sharing.

Answer 1

Текущий код создает в методе разбиения либо бесконечный цикл, либо ArrayIndexOutOfBoundsException в зависимости от выбранного вами массива чисел.Возможное исправление, например:

private int partition(int a[], int left, int right) {
    int i = left, j = right, temp;
    int pivot = a[j];
    while (i <= j) {
        if (a[i] > pivot) {
            temp = a[i];
            for (int k = i; k < right; k++) { // remove a[i] and move all elements...
                a[k] = a[k + 1];              // ...following a[i] to the left
            }
            j--;                              // decrement pivot's index
            a[right] = temp;                  // move a[i] to the right end
        } else {
            i++;
        }
    }
    return j;                                 // return pivot's modified index
}

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

private int[] sort(int[] numbers, int left, int right) {
    int x = partition(numbers, left, right);
    if (left < right) { // left boundary smaller than right one
        sort(numbers, left, x - 1);
        sort(numbers, x + 1, right); 
    }
    return numbers;
}