Не удалось устранить ошибку при использовании последнего элемента в качестве точки разворота в быстрой сортировке

Question

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

partitionFirst() функция использует первый элемент в качестве точки разворота partitionLast() функция использует последний элемент в качестве точки разворота

Код прерывается в строке 75 и строке 77, которые я упоминал в коде. При использовании partitionLast()

Если вы заметите в partitionLast(), я возвратил логику пивота по-другому, имея в виду случай, когда пивот всегда будет меньше элементов. Например. {7 8 9 4 5 6 | 3 | } где 3 - это раздел

Будет полезно, если кто-нибудь укажет на ошибку в коде. Также не стесняйтесь предложить оптимизацию, если таковые имеются.

public class QuickSort {
public void swap(int[] arr, int i, int j)
{
    if(i!=j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

public int partitionFirst(int arr[], int start,int end)
{
    int j = start + 1;
    int pivot = arr[start]; 
    for(int i=start+1;i<end;i++)
    {
        if(pivot > arr[i])
        {
            swap(arr,i,j);
            j++;
        }
    }
    swap(arr,start,j-1);
    return (j-1);
}

public int partitionLast(int arr[], int start,int end)
{
    int j = start;
    int pivot = arr[(end - 1)]; 
    for(int i=start;i < end - 1  ;i++)
    {
        if(pivot > arr[i])
        {
            swap(arr,i,j);
            j++;
        }
    }
    if((j - 1) < 0)
    {
        swap(arr,end-1 ,j);
        return j;
    }
    else
    {
        swap(arr,end-1 ,(j-1));
        return (j-1);
    }
}

public void QuickSort(int arr[], int start,int end)
{
    if(end > start)
    {

        int p = partitionLast(arr, start, end); //75 line
        QuickSort(arr,start, p);
        QuickSort(arr,p+1,end); //77 line
    }
    return;
}

public static void main(String args[]) throws FileNotFoundException
{
    int[] brr = {1,6,8,2,3,4};
    QuickSort ob1 = new QuickSort();
    ob1.QuickSort(brr,0,brr.length);
}

}

/ * Исключение в потоке "main" java.lang.StackOverflowError на QuickSort.QuickSort (QuickSort.java:75) на QuickSort.QuickSort (QuickSort.java:77) на QuickSort.QuickSort (QuickSort.java:77). ...... * /

Answer 1

Все сводится к замене правильного элемента с помощью оси:

public int partitionLast(int arr[], int start,int end)
{
    int j = start;
    int pivot = arr[(end - 1)];
    for(int i=start;i < end - 1  ;i++)
    {
        if(pivot > arr[i])
        {
            swap(arr,i,j);
            j++;
        }
    }
    swap(arr,end-1,j);
    return (j);
}