ArrayIndexOutOfBoundsException - Quicksort Algorithm

Question

So this is my code. The error is ArrayIndexOutOfBoundsException, below I have mentioned it. Please help me find the cause.

import java.util.Scanner;

public class sort {

    public static void main(String args[]){
        Scanner s = new Scanner(System.in);
        System.out.println("Enter the number of entries");
        int[] arr = new int[s.nextInt()];
        System.out.println("Enter the numbers");
        for(int i=0;i<arr.length;i++)
            arr[i] = s.nextInt();
        s.close();
        QuickSort.sort(arr);
        for(int i=0;i<arr.length;i++)
            System.out.print(arr[i]+" ");
    }
}

public class QuickSort {

    private static int partition(int[] arr, int hi, int lo){
        int i=lo,j=hi+1,swap=0;
        while(true){
            while(arr[++i]<arr[lo])
                if(i==hi)break;
            while(arr[--j]>arr[lo]) \\error line
                if(j==lo)break;
            if(j<=i)break;
            swap=arr[i];
            arr[i]=arr[j];
            arr[j]=swap;
        }
        swap=arr[lo];
        arr[lo]=arr[j];
        arr[j]=swap;
        return j;   
    }
    public static void sort(int[] arr){
        sort(arr,arr.length-1,0);
    }
    private static void sort(int[] arr,int hi,int lo){
        int j = partition(arr,hi,lo);
        sort(arr,j-1,lo);
        sort(arr,hi,j+1);
    }

}

Error:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1 at riku.QuickSort.partition(QuickSort.java:10) at riku.QuickSort.sort(QuickSort.java:28) at riku.QuickSort.sort(QuickSort.java:29) at riku.QuickSort.sort(QuickSort.java:29) at riku.QuickSort.sort(QuickSort.java:29) at riku.QuickSort.sort(QuickSort.java:25) at riku.sort.main(sort.java:12) this is the complete error log

In the exception you get the line number where it is thrown, it should help you (and us if you show us which line it is) — Krzysztof Krasoń, Jul 20 '16 at 19:53
What is the error message? It should give you the line number the error occurred on, and the value of the offending index. — FredK, Jul 20 '16 at 19:53
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1 at riku.QuickSort.partition(QuickSort.java:10) at riku.QuickSort.sort(QuickSort.java:28) at riku.QuickSort.sort(QuickSort.java:29) at riku.QuickSort.sort(QuickSort.java:29) at riku.QuickSort.sort(QuickSort.java:29) at riku.QuickSort.sort(QuickSort.java:25) at riku.sort.main(sort.java:12) this is the complete error log — Anshuman Acharya, Jul 20 '16 at 19:54
And what is the value of the index as reported by the error message? — FredK, Jul 20 '16 at 19:55
lo is 0...j is -1 that much i figured but i have a check on j that it breaks off the loops when j==lo..so i dont get how j is -1 — Anshuman Acharya, Jul 20 '16 at 20:02

score 1 · Accepted Answer · answered Jul 20 '16 at 20:08

1

j getting to 0, then arr[--j] is evaluating to arr[-1] you have to make sure that index never gets below zero.

Another approach would be to use recursion, it would be much simpler but can cause stack overflow for large arrays.

answered Jul 20 '16 at 20:08

Jonas Fagundes

1,519
1
11
18

then why doesnt it break off at j==lo? – Anshuman Acharya Jul 20 '16 at 20:09
When it gets there it already evaluated the condition in the loop, what generates the error. – Jonas Fagundes Jul 20 '16 at 20:12
set j=hi and then j-- ? inplace of j=hi+1 and --j – Anshuman Acharya Jul 20 '16 at 20:16
Just change from `while(arr[--j]>arr[lo])` to `while(arr[j--]>arr[lo])`. Overall the code is error prone, does your implementation has to be in-place? – Jonas Fagundes Jul 20 '16 at 20:20
`while(arr[--j]>arr[lo]) if(j==lo)break;` will always exit with j>=0 as long as j was > 0 initially. So the problem seems to be that j can start out equal to zero. – FredK Jul 20 '16 at 20:23
i have just started coding...how do i minimise my code to errors? and no implementation doesnt have to be in place – Anshuman Acharya Jul 20 '16 at 20:24
initialised j to hi+1..dont know how it could be <0 – Anshuman Acharya Jul 20 '16 at 20:27
yeah i think thats it FredK.. thanks for the help although i dont know how to solve it – Anshuman Acharya Jul 20 '16 at 20:29
`int j = partition(arr,hi,lo);` can set j<2, then the you call `sort(arr,j-1,lo);` so the second argument is less than 1. ` – FredK Jul 20 '16 at 20:33
A few tips: 1. Don't use arrays directly in java, use ArrayList so you have the List abstraction but backed up by array. 2. Use java.util.stream.Collectors.partitioningBy to partition your set in smaller and equalOrGreater. 3. Use an recursive algorithm, `List sort(List unorderedList)` and after your select the pivot and make the partition all your program has to do is `return sort(smaller).addAll(Arrays.asList(pivot)).addAll(sort(equalOrGreater);`. No more mess with array indexes :) – Jonas Fagundes Jul 20 '16 at 20:40
On the beginning of this method you have to put `if (unorderedList.isEmpty()) return unorderedList;` in the `else` put the algorithm I described before. This will stop the recursion when the list finally gets empty. – Jonas Fagundes Jul 20 '16 at 20:47

danny · Answer 2 · 2016-07-20T20:27:14.200

0

Your -- is before your variable j, which means that the variable first is decreased, then read.

Try to put it after the variable like this: arr[j--].

If it won't work, try setting j=hi+1to j=hi.

edited Jul 20 '16 at 20:27

answered Jul 20 '16 at 20:19

danny

358
2
14

tried that! error is in the swap line now after the while loop – Anshuman Acharya Jul 20 '16 at 20:21
Now you're out of the upper bound of the array? Wouldn't that mean, that the `i` has the same problem as the `j` had? Try to change the increasing for `i` from `++i` to `i++`. – danny Jul 20 '16 at 20:31
no the post decrement of j is causing it to give an error after the while loop has completed on a different line the line where i m swapping same j same error different line – Anshuman Acharya Jul 20 '16 at 20:33
Your problem lies deeper. I reproduced your error and the problem is that `j` is returned from `partition()` and in that moment `j` is always 0, what means that the second argument (int hi) in `partition` is always 0. This leads to the effect that `j` is -1 at the second call. – danny Jul 20 '16 at 20:59
yup...i got it thanx :D – Anshuman Acharya Jul 21 '16 at 21:39

score 0 · Answer 3 · edited Aug 29 '21 at 06:39

0

You can try the following. This way the break statement is not needed.

while(j >= 0 && arr[j] > arr[lo])
    j--;

edited Aug 29 '21 at 06:39

Sujit

1,653
2
9
25

answered Aug 19 '21 at 03:00

Mohammad Sayem

1
1

ArrayIndexOutOfBoundsException - Quicksort Algorithm

3 Answers3