Insert into an already-sorted list

Question

With Java, I have a class, known as TestClass, which has a member named Name, which is a string. I also have an ArrayList of this type, which is already sorted alphabetically by Name. What I want to do is find the best index in which to put a new instance of TestClass. The best approach I could come up with so far is this:

public static int findBestIndex(char entry, ArrayList<TestClass> list){
    int desiredIndex = -1;
    int oldPivot = list.size();
    int pivot = list.size()/2;
    do
    {
        char test = list.get(pivot).Name.charAt(0);
        if (test == entry)
        {
            desiredIndex = pivot;
        }
        else if (Math.abs(oldPivot - pivot) <= 1)
        {
            if (test < entry)
            {
                desiredIndex = pivot + 1;
            }
            else
            {
                desiredIndex = pivot - 1;
            }
        }
        else if (test < entry)
        {
            int tempPiv = pivot;
            pivot = oldPivot - (oldPivot - pivot)/2;
            oldPivot = tempPiv;
        }
        else
        {
            int tempPiv = pivot;
            pivot = pivot - (oldPivot - pivot)/2;
            oldPivot = tempPiv;
        }

    } while (desiredIndex < 0);

    return desiredIndex;
}

Essentially, Break the array in half, check to see if your value goes before, after, or at that point. If it's after, check the first half of the array. Other wise, check the second half. Then, repeat. I understand that this method only tests by the first character, but that's easily fixed, and not relevant to my main problem. For some scenarios, this approach works well enough. For most, it works horribly. I assume that it isn't finding the new pivot point properly, and if that's the case, how would I fix it?

Edit: For clarification, I'm using this for an inventory system, so I'm not sure a LinkedList would be appropriate. I'm using an ArrayList because they are more familiar to me, and thus would be easier to translate into another language, if needed (which is likely, at the moment, might be moving over to C#). I'm trying to avoid things like Comparable for that reason, as I'd have to completely re-write if C# lacks it.

Edit part Duex: Figured out what I was doing wrong. Instead of using the previous pivot point, I should have been setting and changing the boundaries of the area I was checking, and creating the new pivot based on that.

Answer 1

It might not be a good idea to use a SortedSet (e.g. a TreeSet) for this, because Set‘s don't allow duplicate elements. If you have duplicate elements (i.e. TestClass instances with the same name), then a List should be used. To insert an element into an already sorted list is as simple as this:

void insert(List<TestClass> list, TestClass element) {
    int index = Collections.binarySearch(list, element, Comparator.comparing(TestClass::getName));
    if (index < 0) {
        index = -index - 1;
    }
    list.add(index, element);
}

This code requires Java 8 or later, but can be rewritten to work in older Java versions as well.

Answer 2

As already pointed out, there is no reason to implement this by yourself, simple code example:

    class FooBar implements Comparable<FooBar> {

        String name;

        @Override
        public int compareTo(FooBar other) {
           return name.compareTo(other.name);
        }
    }

    TreeSet<FooBar> foobarSet = new TreeSet<>();
    FooBar f1;
    foobarSet.add(new FooBar("2"));
    foobarSet.add(f1 = new FooBar("1"));

    int index = foobarSet.headSet(f1).size();

(Based on How to find the index of an element in a TreeSet?)

Answer 3

I think the problem is in this bit of the code:

else if (test < entry)
{
    int tempPiv = pivot;
    pivot = oldPivot - (oldPivot - pivot)/2;
    oldPivot = tempPiv;
}
else
{
    int tempPiv = pivot;
    pivot = pivot - (oldPivot - pivot)/2;
    oldPivot = tempPiv;
}

You are peforming the same actions wether test < entry or wether test > entry. This will lead to a linear search when the item you are searching for is at the start of the array.

I prefer to use (low and high) like

high = list.size();
low = 0;

do {
   pivot = (high + low) / 2;
   if (test < entry) {
      low = pivot;
   } else if (test > entry) {
      high = pivot
   } else {
      ....
   }
} while ...;

Answer 4

You should use something like a PriorityQueue that already has a sense of order. Inserting into a collection with a sense of order will automatically place the element in the correct place with minimal time(usually log(n) or less).

If you want to do arbitrary inserts without this, then I would suggest using a LinkedList that won't have to be resorted or completely copied over to insert a single item like the ArrayList you currently have. While finding the correct insert location for a LinkedList will take up to O(n) time, in practice it will still be faster than using a log(n) search for the correct location in an ArrayList, but then needing to copy or sort it afterwards.

Also the code for finding the insert location in a linked list is much simpler.

if (next != null && next.compareTo(insertElement) > 0){
    // You have the right location
}

Answer 5

There are other data structures used could use instead of list like a tree, priority queue etc.

Answer 6

Make a list implementation of your own, and in your add method have these lines:

wrappedList.add(object);
Collections.sort(wrappedList);