CODEWITHSUNDEEP
javaarrayssortingquicksort
Chris
Chris

Reputation: 119

Bug help, Array out of bounds at high values

I am getting an out of bounds exception thrown when I use this median of medians code to find a given location of k. I am not sure of the exact size at which it begins throwing the error, but the code works for arrays of size < 75, and the error starts when I exceed array size 100.

private static int mmQuickSortRecursive(Integer[] a, int k) {
    if (a.length <= 10)
    {
        Arrays.sort(a);
        return a[k-1];
    }
    int n = a.length;
    // partition L into subsets S[i] of five elements each (n/5 subsets).
    ArrayList<Integer[]> list = new ArrayList<Integer[]>();
    int cnt = 0;
    int m = n/5;
    for( int i = 0; i < m; i++ ) {
        Integer[] arr = new Integer[5];
        for( int j = 0; j < 5; j++ ) {
            if( cnt == n ) 
                break;
            arr[j] = a[cnt++];
        }
        Arrays.sort(arr);
        list.add(arr);
    }
    Integer[] x = new Integer[m];
    for (int i = 0; i< m; i++ ) {
        x[i] = list.get(i)[2];
    }
    int v = x[0];
    if(x.length > 2) {
                    ///////// ERROR THROWN ON BELOW LINE /////////////////
        v = (x.length%2 == 0)? x[x.length%2-1]: x[x.length/2];
    }
    //    partition L into 3 parts, L1<M, L2=M, L3>M
    Integer[] l = partition_left( a, v );
    Integer[] r = partition_right( a, v );
    if( k == l.length+1 ) {
        return v;
    } else if( k <= l.length ){
        return mmQuickSortRecursive(l,k);                               
    } else {
        return mmQuickSortRecursive(r,k-l.length-1);                            
    }       

}

Upvotes: 1

Views: 52

Answers (1)

Judge Mental
Judge Mental

Reputation: 5239

v = (x.length%2 == 0)? x[x.length%2-1]: x[x.length/2];

Seems wrong. shouldn't it be

v = (x.length%2 == 0)? x[x.length/2]: x[x.length/2-1];

Upvotes: 1

Related Questions