How do I order an array of objects based on one of their attributes?

Question

I have an object called a Contact that has a bunch of attributes. I also have an array of Contacts called Contact_List, and I have to write a method for the Contact_List that will add a Contact object to it. That part is easy, but it has to ensure that all of the Contacts within it are in order based on their last names. I already have an accessor called getLastName that returns the String of their last name, but how do I make the method add the contact and order them? Please Help, this is due in an hour and a half!

 public void add(Contact frnd)
 {
     if(numContacts == MAX_CONTACTS) // If the List is already full
     {
      System.out.println("The Contact List is already at Maximum Capicity");
     }
     else
     {
      numContacts += 1; // There is one more Contact
      Contact_List[numContacts - 1] = frnd; // Assigns the Last Open Spot the new Contact
     }
 }

Answer 1

Have a look at Arrays.sort() which accepts a Comparator where you can implement whatever logic you want for ordering your objects. There's also a Collections.sort() if you want to sort Lists instead of arrays.

EDIT: I'm not quite sure I'm doing the right thing, but I'll try to answer your specific question with how I would implement such a requirement in Java. However, this won't be very helpful if you must use an array internally and handle the array (re)allocation and implement the sorting logic manually.

private final Set<Contact> contacts = new TreeSet<Contact>( new Comparator<Contact>() {
    @Override
    public int compare(Contact c1, Contact c2) {
        return c1.getLastName().compareTo(c2.getLastName());
    }
});

public void add(Contact contact) {
    contacts.add(contact);
}

public Contact[] getContacts() {
    return contacts.toArray(new Contact[contacts.size()]);
}

Besides, if the last name provides the natural order of those contacts, I would rather make the Contact class implement Comparable and thus eliminate the need for providing a Comparator to the TreeSet.

Answer 2

This could work

public static void add(Contact frnd) {
    if (contactList.length == MAX_CONTACTS) {
        throw new IllegalStateException("The Contact List is already at Maximum Capicity");
    }
    int i = Arrays.binarySearch(contactList, frnd, new Comparator<Contact>() {
        public int compare(Contact o1, Contact o2) {
            return o1.getLastName().compareTo(o2.getLastName());
        }
    });
    if (i < 0) {
        i = -i - 1;
    }
    Contact[] temp = new Contact[contactList.length + 1];
    System.arraycopy(contactList, 0, temp, 0, i);
    temp[i] = frnd;
    if (i < contactList.length) {
        System.arraycopy(contactList, i, temp, i + 1, contactList.length - i);
    }
    contactList = temp;
}

But for this task List or TreeSet seem to be more appropriate.

Answer 3

The simplest thing you can do for your example is sort the elements as you add them to the array.

You would replace your

  numContacts += 1; // There is one more Contact
  Contact_List[numContacts - 1] = frnd; // Assigns the Last Open Spot the new Contact

With code that traverses the array and finds the right place to insert the item. INSTEAD of simply placing the item at the end.

For example, let's say you have four people in your array with these last names.

Anthony
Adam
Cindy
Dirk

Now you insert contact Brian

You would want your loop to step through the array, checking the first position to see if it belongs in the 0th index. In this case Anthony comes before Brian, so it doesn't. Then you check the 1st index, but in this case Adam comes before Brian, so it doesn't. Then you check the 2nd index. Aha! Brian comes AFTER Adam, but before Cindy. This is the correct place to insert Brian into your array. Now your array looks like this.

Anthony
Adam
Brian
Cindy
Dirk

If you write the "insert" method in this manner you can guarantee that the array always remains sorted as you add items. Your life will be made a LOT easier by using ArrayList instead of an array. In all the time that I've used Java I've used ArrayList over Array 99.9% of the time.

Answer 4

The simple solution is to add the contact at the next position (as you are doing now) then sort the array after adding, so it's always in the correct sorted order:

After adding the last contact, use a custom comparator to sort:

if (numContacts == MAX_CONTACTS) {
Arrays.sort(contacts, new Comparator<Contact>() {
    public int compare(Contact o1, Contact o2) {
        return o1.getLastName().compareTo(o2.getLastName());
    }
});
}

Also, these two lines:

numContacts += 1;
Contact_List[numContacts - 1] = frnd;

May be replaced with simply:

Contact_List[numContacts++] = frnd;