bluedroid bluedroid - 17 days ago 7
Java Question

Merge Sort: IndexOutOfBoundsException

The following merge sort works well with int array(obviously with required changes) but throws IndexOutOfBoundsException with ArrayList collection of Student objects I created.
I have divided the unsorted array list into n sub array lists, each containing 1 element (a list of 1 element is considered sorted).
Repeatedly merge sub arrays to produce new sorted sub arrays until there is only 1 sub array remaining. This will be the sorted list.

public class MergeSort {

public void mergeSort(ArrayList<Student> array) {
if (array.size() > 1) {
ArrayList<Student> left = leftHalf(array);
ArrayList<Student> right = rightHalf(array);

mergeSort(left);
mergeSort(right);

merge(array, left, right);
}
}

public ArrayList<Student> leftHalf(ArrayList<Student> array) {
int size1 = array.size() / 2;
ArrayList<Student> left = new ArrayList<>(size1);
for (int i = 0; i < size1; i++) {
left.set(i, array.get(i));
}
return left;
}

public ArrayList<Student> rightHalf(ArrayList<Student> array) {
int size1 = array.size() / 2;
int size2 = array.size() - size1;
ArrayList<Student> right = new ArrayList<>(size2);
for (int i = 0; i < size2; i++) {
right.set(i, array.get(i + size1));
}
return right;
}

public void merge(ArrayList<Student> result, ArrayList<Student> left, ArrayList<Student> right) {
int i1 = 0;
int i2 = 0;

for (int i = 0; i < result.size(); i++) {
if (i2 >= right.size() || (i1 < left.size() && (left.get(i1).compareTo(right.get(i2)) <= 0))) {
result.set(i, left.get(i1));
i1++;
} else {
result.set(i, right.get(i2));
i2++;
}
}
}
}


Student Object:

public class Student implements Comparable<Student> {
String firstName, midName, lastName;
int ID;

public Student(String lastName, String firstName, String midName, int ID) {
this.firstName = firstName;
this.midName = midName;
this.lastName = lastName;
this.ID = ID;
}

@Override
public int compareTo(Student s) {
if (!(this.lastName.equals(s.lastName))) {
return (this.lastName).compareTo(s.lastName);
} else if (!(this.firstName.equals(s.firstName))) {
return (this.firstName).compareTo(s.firstName);
} else if (!(this.lastName.equals(s.lastName))) {
return (this.lastName).compareTo(s.lastName);
} else if (this.ID > s.ID) {
return 1;
} else if (this.ID < s.ID) {
return -1;
} else return 0;
}

@Override
public String toString() {
return lastName + ", " + firstName + " " + midName + " " + ID;
}
}

Answer

Update your leftHalf and rightHalf to use left.add(array.get(i)); and right.add(array.get(i + size1)); instead of using left.set(i, array.get(i)); and right.set(i, array.get(i + size1));

ArrayList set method will throw IndexOutOfBoundsException if your index is greater than or equal to size of ArrayList

 public ArrayList<Student> leftHalf(ArrayList<Student> array) {
        int size1 = array.size() / 2;
        ArrayList<Student> left = new ArrayList<>(size1);
        for (int i = 0; i < size1; i++) {
            left.add(array.get(i));
        }
        return left;
    }

    public ArrayList<Student> rightHalf(ArrayList<Student> array) {
        int size1 = array.size() / 2;
        int size2 = array.size() - size1;
        ArrayList<Student> right = new ArrayList<>(size2);
        for (int i = 0; i < size2; i++) {
            right.add(array.get(i + size1));
        }
        return right;
    }
Comments