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.

Solution 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.

Solution 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?)

Solution 3

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

Solution 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
}

Solution 5

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 ...;

View more solutions

Comments

[fge]

Why don't you just insert all elements, then use Collections.sort()?

[user2423158]

@fge, resorting after each insertion would likely be the slowest way to go, although speed isn't my largest concern, since there will not likely be many objects being shifted in and out rapidly.

[Stony]

I also think we should use sortable list. In the answer, we use Comparable. And another option is use Comparator.

[user2423158]

I'm not sure a PriorityQueue or LinkedList would be best for what I'm using this for (Which I really should have mentioned in the original post, and have now fixed).

[user2423158]

I went with Arraylist due to familiarity, and for ease of access to any given element. Another data structure, however, may be a good idea, although I'd have to do some research first.

[greedybuddha]

Well, I have to say your reason of not wanting to use a LinkedList b/c it would be easier to translate an ArrayList to C# is not correct. Both would equally easy to translate ( I would even say the LinkedList easier). The most important thing though is you cannot insert an element into the middle of an ArrayList without shifting all elements after it. This involves copying that part of the ArrayList, significantly slower than a LinkedList insert. Basically, if you are looking for efficiency, you are using the wrong datastructure.

[Matthieu]

Why isn't that the accepted answer (if @user2423158 wanted to accept one...)? It has the key to work in O(log(n)) on arrays. Thanks!

[Bruce Martin]

@Matthieu thank you for the up vote, I suspect the user wanted his question answered and had no interest after that

[Ravjit Singh]

It's not about trees. Set doesn't allow duplicate elements

[Daniel Beer]

Thank you for pointing that out. I changed the wording accordingly.