willielf willielf - 3 months ago 13
Java Question

I have an issue with implementing Merge Sort for Java

public static void main(String[] args) {
int[] test = {5,4,3,5,7,5,1,5,96};
System.out.print("Before: ");
printList(test);
mergeSort(test, 1, test.length);
//System.out.print("After: ");
//printList(test);
}

public static void printList(int[] test){
for (int i= 0; i < test.length; i++){
System.out.print(test[i] + " ");
}
System.out.println();
}

public static void merge(int[] A, int p, int q, int r){
int n1 = q - p + 1;
int n2 = r - q;

int[] L = new int[n1];
int[] R = new int[n2];

for(int i = 1; i <= n1; i++){
L[i] = A[p+i-1];
}
for (int j = 1; j <= n2; j++){
R[j] = A[q+j];
}
int i = 1;
int j = 1;

for (int k=p; i <= r; i++){
if (i > n1){
A[k] = R[j];
j++;
}
else if (j > n2){
A[k] = L[i];
i++;
}
else if (L[i] <= R[j]){
A[k] = L[i];
i++;
}
else{
A[k] = R[j];
j++;
}
}
}

public static void mergeSort(int[] A, int p, int r){
if (p < r){
int q = (p + r) / 2;
mergeSort(A, p, q);
mergeSort(A, q+1, r);
merge(A, p, q, r);
}
}


I am trying to implement merge sort on a test array, but I am not sure why I am getting an ArrayIndexOutOfBoundsException error on this. The assignment is to change the merge sort code to not use any sentinels when searching.

Before: 5 4 3 5 7 5 1 5 96
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 1
at Lab1_2.merge(Lab1_2.java:28)
at Lab1_2.mergeSort(Lab1_2.java:61)
at Lab1_2.mergeSort(Lab1_2.java:59)
at Lab1_2.mergeSort(Lab1_2.java:59)
at Lab1_2.mergeSort(Lab1_2.java:59)
at Lab1_2.main(Lab1_2.java:8)


This is the error message that I get.

Answer

you are getting ArrayIndexOutOfBoundsException run time exception because you are try to accessing array out of your array boundary (limits). in merge method your statements like

 int[] L = new int[n1];

you declare array of size n1 you can get element at index from 0 to n-1. but you are try to storing element at index n1. which is not possible because as we know array having element from 0 to size-1 (here size is length of array) this is one of the reason. you have issue some other places. So I edit your code and hope following code work for you.

/* package whatever; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;


class Ideone
    {
    public static void main (String[] args) throws java.lang.Exception
    {
    // your code goes here
        int[] test = {5,4,3,5,7,5,1,5,96};
    System.out.print("Before: ");
    printList(test);
    mergeSort(test, 0, test.length-1);
    System.out.print("After:  ");
    printList(test);
}

public static void printList(int[] test){
for (int i= 0; i < test.length; i++){
    System.out.print(test[i] + " ");
}
System.out.println();
}

public static void merge(int[] A, int p, int q, int r){
int n1 = q - p + 1;
int n2 = r - q;

int[] L = new int[n1];
int[] R = new int[n2];

for(int i = 0; i < n1; i++){
    L[i] = A[p+i];
}
for (int j = 0; j < n2; j++){
    R[j] = A[q+j+1];
}
//int i = 0;
//int j = 0;

   /* for (int k=p; i <= r; i++){
    if (i > n1){
        A[k] = R[j];
        j++;
    }
    else if (j > n2){
        A[k] = L[i];
        i++;
    }
    else if (L[i] <= R[j]){
        A[k] = L[i];
        i++;
    }
    else{
        A[k] = R[j];
        j++;
    }
    }*/

       int i = 0, j = 0;


    int k = p;
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            A[k] = L[i];
            i++;
        }
        else
        {
            A[k] = R[j];
            j++;
        }
        k++;
    }


    while (i < n1)
    {
        A[k] = L[i];
        i++;
        k++;
    }


    while (j < n2)
    {
        A[k] = R[j];
        j++;
        k++;
    }

}

public static void mergeSort(int[] A, int p, int r){
if (p < r){
    int q = (p + r) / 2;
    mergeSort(A, p, q);
    mergeSort(A, q+1, r);
    merge(A, p, q, r);
}
}

}