Rearranging arrays - java

Question

I'm trying to rearrange my Person array according to age from youngest to eldest using the code below.

public class Trial {

    public static void main(String[] args){

        Person[] person = new Person[3];

        person[0] = new Person("Jerome", 21);
        person[1] = new Person("Jam", 16);
        person[2] = new Person("Imelda", 53);

        for(int i=0; i<person.length;i++){
            System.out.println(person[i].getName() + " " + person[i].getAge());
        }

        String name = "";
        int age = 0;
        int counter = 0;

        for(int i=1;i<person.length;i++){

            name = person[i].getName();
            age = person[i].getAge();

            counter = i - 1;

            while(i>-1&&person[counter].getAge()>age){
                person[counter+1].setAge(person[counter].getAge());
                person[counter+1].setName(person[counter].getName());
                counter -= 1;
            }


            person[counter+1].setAge(age);
            person[counter+1].setName(name);

        }

        for(int i=0; i<person.length;i++){
            System.out.println(person[i].getName() + " " + person[i].getAge());
        }

    }
}

The algorithm runs smoothly with arrays of integer but here, I get this error.

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
    at com.example.java.Trial.main(Trial.java:28)

This is where the error points to

while(i>-1&&person[counter].getAge()>age){
                person[counter+1].setAge(person[counter].getAge());
                person[counter+1].setName(person[counter].getName());
                counter -= 1;
            }

Am I doing something wrong? Or is there another way of arranging object arrays according to a specific variable?

Answer 1

The core problem is indeed located there:

while(i>-1&&person[counter].getAge()>age){
    person[counter+1].setAge(person[counter].getAge());
    person[counter+1].setName(person[counter].getName());
    counter -= 1;
}

In the while loop, you do a bounds-check on i (i > -1), but you use counter instead. So in order to solve the core problem, you have use counter instead of i:

while(counter>-1&&person[counter].getAge()>age){
    person[counter+1].setAge(person[counter].getAge());
    person[counter+1].setName(person[counter].getName());
    counter -= 1;
}

Nevertheless, that's not a good way to sort objects in an array. Because of several reasons:

• Instead of swapping objects, you exchange the state of these objects. Imagine that later in the project, you have to add a new field to Person, then your algorithm is ruined. Furthermore it is possible that there are other references to that Person that will see its name and age change.
• You are implementing an insertion sort algorithm whereas QuickSort and MergeSort outperform insertion sort significantly.

Problem with exchanging state

If you exchange the state of your objects, that's something different than exchanging their position in the array. Imagine that you wish to extend your program: now people can be married. It means for instance you hold an array somewhere of a Person that is married tot Bob. Say Bob is married to Alice. If later you modify the name of Bob to Cindy, all of a sudden Cindy is married to Alice.

You can solve that problem, by rewriting your code to:

for(int i=1;i<person.length;i++) {
    Person toSwap = person[i];
    counter = i - 1;
    while(counter >-1 &&person[counter].getAge()>age) {
        person[counter+1] = person[counter];
        counter -= 1;
    }
    Person[counter+1] = toSwap;
}

Furthermore it is advicable to turn a while in a for, because there is less chance of producing an infinite loop:

for(int i=1;i<person.length;i++) {
    Person toSwap = person[i];
    for(counter = i-1; counter >-1 &&person[counter].getAge()>age; counter--) {
        person[counter+1] = person[counter];
    }
    Person[counter+1] = toSwap;
}

Sorting algorithms

You basically implement a version of insertion sort. Insertion sort takes an object, looks for all larger (or smaller) objects, shifts these objects one to the right (left) and then positions the object on the correct position. This runs worst case in O(n²) or quadratic time. It means that in the worst case if you double the length of your list, it will take four times more time to solve the problem.

Computer scientists have come up with better ways to sort like QuickSort and MergeSort. MergeSort for instance runs in O(n log n). This means that if you double the length of your list, the time it takes to sort doubles as well and there is one time unit added. What that time unit is (one millisecond, nanosecond, 78 seconds,...) is unknown, but eventually, if the list is large enough, MergeSort will outperform InsertionSort for an unsorted list.

Using builtins

Java offers a large amount of classes, methods and algorithms. By using these algorithms, you use a lot of research in how things should be done error-safe, efficient and without much/any side-effects.

In order to do an error-safe and fast sorting, you can use Arrays.sort(T[],IComparator<T>).

Answer 2

If you make Person implement Comparable, you can use Arrays.sort(...) to do this for you!

public class Person implements Comparable<Person> {
    // Existing class implementation

    @Override
    public int compareTo(Person p) {
        return p2.age - this.age;
    }
}

EDIT: Alternatively, you can implement your compareTo method directly inline when Arrays.sort() is called (ie: no modification to Person is required):

Arrays.sort(personArray, new Comparator<Person>() {
    @Override
    public int compare(Person p1, Person p2) {
        return p2.age - p1.age;
    }
});

If you're running Java 8, this can be shortened even further using a lambda expression:

Arrays.sort(personArray, (p1, p2) -> p2.age - p1.age);

Answer 3

Try to change this:

     for(int i=1;i<person.length;i++){

To

     for(int i=1;i<=person.length;i++){