Styjun

I'm given the task of adding a value into an ArrayList alphabetically (by lastname first, and firstname if lastnames are the same),I'm not allowed to sort the ArrayList once all the inputs are given. What I am suppose to do is determine the location of where the value should be each time an input is given and place it there. Example values: Inputs are John Doe, Bryan Sully, Harry Ache, Ali Doe, Bry Dyre , Output should be Harry Ache, Ali Doe, John Doe, Bry Dyre, Bryan Sully. However, in cases where there are two of the same last names, what will occur is Harry Ache, Ali Doe, Bry Dyre, John Doe, Bryan Sully, why?

ArrayList<Person> list = new ArrayList<Person>();

public void addPerson(Person p)
 if(list.size() == 0)
 list.add(p);
 else
 for(Person pp: list)
 int getIndex = list.indexOf(pp);
 int lOrder = p.getLastName().compareTo(pp.getLastName());
 if(lOrder > 0)
 list.add(getIndex + 1, p);
 break;
 else if(lOrder == 0)
 int fOrder = p.getFirstName().compareTo(pp.getFirstName());
 if(fOrder > 0)
 list.add(getIndex, p);
 break;
 else 
 list.add(getIndex + 1, p);
 break;
 
 else 
 list.add(getIndex, p);
 break;
 
 
 
 

One issue with your code is that you are making an insertion after a single iteration of your loop, inserting Person p only in comparison to the first Person in the list.

Here is an improved implementation:

public void addPerson(Person person) 
 if (list.isEmpty()) 
 list.add(p);
 else 
 // the position where you will insert the Person;
 // default value is list.size(), so it can be added to the end
 int position = list.size();

 Person p;
 for (int i = 0; i < list.size(); i++) 
 p = list.get(i);

 // if the comparison result is > 0, you found the first Person
 // in the list that comes alphabetically after;
 // Insert person before it, at position i
 if (compare(p, person) > 0) 
 position = i;
 break; // only break now that you've found the insert position
 
 
 list.add(person, position);
 


/**
 * @return 0 if both Persons p1 & p2 have the same names, 
 * a positive number if p1 is lexicographically greater than p2, 
 * or a negative number if p1 is lexicographically less than p2 
 */
private int compare(Person p1, Person p2) 
 int result = p1.getLastName().compareTo(p2.getLastName());
 if (result == 0) 
 result = p1.getFirstName().compareTo(p2.getFirstName());
 
 return result;

As others suggested, implementing the Comparable interface in Person if possible can also help create a cleaner implementation.

Few improvements.

• You are better off if you can iterate the list using the index like
  for(int i = 0; i < array.size(); i++)




• You need not have to check for lastName and firstName separately. You can just compare both of them together (p.lastName + p.firstName).compareTo(pp.lastName + pp.firstName) and act upon the result. As you already have the index of the current element, you just have to check if you just insert the new item on the same index or not.

Here is a sample implementation

static void addPerson(Person person) 
 for (int i = 0; i < sortedList.size(); i++) 
 var existingPerson = sortedList.get(i);
 var compareResult = compare(existingPerson, person);
 if (compareResult > 0) 
 sortedList.add(i, person);
 return;
 
 
 sortedList.add(person);


static int compare(Person p1, Person p2) 
 return (p1.lastName + p1.firstName).compareTo(p2.lastName + p2.firstName);

The problem with your algorithm, is that you always looking at the first person in the target list, and making decisions solely on that person, notice how all your "branches" have a break statement at the end?

I understand your "reason" for adding all those break statements, those make sure the new person always gets inserted into the list, when it doesn't match, the same reason why your first check if the list is empty.

To properly implement an "insertion sort" system, you actually need to loop over all the indexes of your list.

An simple "insertion sort" algorithm looks like this:

1. Loop over the target list


2. Check if existing entry is "bigger" than the newly person


3. If the existing entry is bigger, we need to move that entry (all all remaining entries) up 1 spot, insert out entry, and abort
   


4. If we are done looping, and we didn't abort in the above steps, insert our entry at the end of the list.

ArrayList<Person> list = new ArrayList<Person>();

public void addPerson(Person p)
 // Loop
 int size = list.size();
 for(int getIndex = 0; getIndex < size; getIndex++)
 Person pp = list.get(getIndex);
 // Compare
 int compare = p.getLastName().compareTo(pp.getLastName());
 if (compare > 0) 
 continue;
 else if(compare == 0) 
 if (p.getFirstName().compareTo(pp.getFirstName()) > 0) 
 continue;
 
 
 // Add in existing slot
 list.add(getIndex, p);
 return;
 
 // Add at the end
 list.add(p);

One hard part of this, is the fact that we have to compare on 2 things for a single person, this makes the compare logic way harder than it needs to be. This can be solved by factoring this part out to a "helper" comparator that does this logic merging for us:

Comparator<Person> compare = Comparator
 .comparing(Person::getLastName)
 .thenComparing(Person::getFirstName);

// Then, inside the above loop:
 ...
 // Compare
 if (compare.compare(p, pp) > 0) 
 continue;
 
 ...