0

i have simple Array

int[] arr = {-1,-3,-5,12,9,0};
Qs(arr,0,arr.length-1);

private static void Qs(int[] arr,int L,int R) {
         if(L>=R) { 
             return;
         }
         int pivot = partition(arr,L,R);

         Qs(arr,L,pivot-1);
         Qs(arr,pivot+1,R);

    }


 private static int partition(int[] arr,int L,int R) {
        int pivot = arr[R];
        int i = L-1;        
        for(int j=0; j <R-1 ; j++) {
            if(arr[j] < pivot) {
                ++i;
                //swap
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
        
        return i+1;
    }

and i keep getting :

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 6
    at QuickSort.partition(QuickSort.java:19)

which is this in function partition:

  int tmp = arr[i];
user63898
  • 29,839
  • 85
  • 272
  • 514
  • 2
    `int i = L-1;` should be `int i = L;`, and then move `i++` after the swap, and at last, replace `return i+1` with `return i`. See also a pseudo reference implementation: https://en.wikipedia.org/wiki/Quicksort#Lomuto_partition_scheme – Lino May 14 '21 at 07:29
  • ok it worked but why ? why i can't do L-1 ? if i like to start from -1 ? how does it related to the array ? – user63898 May 14 '21 at 07:33
  • Well if you increment `i` in the last iteration of the `for` loop, then its possible that `i == arr.length - 1`, when you now add `1` to that `i` at the end of the method, then you have `i == arr.length` which leads to that exception – Lino May 14 '21 at 07:36
  • soory you to tell you that this not working allso look at this link this exactly what i did https://www.softwaretestinghelp.com/quicksort-in-java/#:~:text=Quicksort%20uses%20a%20divide%2Dand,The%20Easy%20Java%20Training%20Series. – user63898 May 14 '21 at 07:53
  • 1
    `arr[j] < pivot` should probably be `arr[j] <= pivot`, also `j = 0` should be `j = L`. And at last you need to swap `arr[i + 1]` with `arr[R]` at the end of the method – Lino May 14 '21 at 08:00

0 Answers0