Sorting a list from the beginning

Question

I have a list of objects that will take lots of adds/removes. I want the list to be sorted according to a certain function.

Right now, everytime I add a new object, I do:

list.add(obj1);
Collections.sort(list1, comparator);

Removing an object doesn't "unsort" the list, so I only need to do this for the add operation.

However, Collections.sort is O(>N) which is not very fast.

Is there any structure in java that allows me to keep a sorted list from the very beginning?

Forgot to mention

I tried to use TreeSet. It allows me to a pass a comparator which will be used for sorting but which will also be used to remove elements which is not what I want. I want it to be sorted but the remove functionality be identical to a list.

Could it be a [SortedSet](https://docs.oracle.com/javase/7/docs/api/java/util/SortedSet.html)? Also check [this](https://stackoverflow.com/questions/4903611/java-list-sorting-is-there-a-way-to-keep-a-list-permantly-sorted-automatically) — BackSlash, Nov 13 '18 at 16:22
It seems that TreeSet is exactly what you need (as long as you don't have any duplicates to worry about). What exactly do you mean by "... which is not what I want"? The remove is only done when you ask it to remove something; it's not compulsory! — DodgyCodeException, Nov 13 '18 at 16:34
@DodgyCodeException I know but when I do `remove(obj)` it seems it uses the comparator to "find" that object instead of removing the actual object. — Afonso Matos, Nov 13 '18 at 16:43
@AfonsoMatos of course it will use the comparator to remove the given object. How else do you expect it to find the object? Perhaps using the equals method? It could use that, but since it already uses the comparator, it takes that as the method to use for equality. — DodgyCodeException, Nov 13 '18 at 16:46
The docs for TIMSort (for `Collections.sort`) state that the "implementation is a stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when the input array is partially sorted, while offering the performance of a traditional mergesort when the input array is randomly ordered.". I'd suspect you can keep using that actually. — Mena, Nov 13 '18 at 16:48
@Mena any sort will still require O(n), which while lower than O(n lg n), is way higher than the easy-to-obtain O(lg n) of finding the right insertion index via Binary Search — tucuxi, Nov 13 '18 at 16:53
@tucuxi good point. Then probably overriding `add` with implementation `super.add(index, element)` where `index` is determined by binary search as Alencar suggests might be worth testing. But that might require looking further into the cost of `add(index, element)` too... — Mena, Nov 13 '18 at 16:54
By the way, "the remove functionality be identical to a list" - do you realise that List's remove method *searches* each and every element in turn in order to find the given object by calling its equals() method? That's an O(N) operation. — DodgyCodeException, Nov 15 '18 at 14:04

tucuxi · Accepted Answer · 2018-11-14T11:31:08.510

As Alencar proposes, use Collections.binarySearch(yourList, key, comparator) to find the correct insert position. This is far faster than looking up the whole list, since binarySearch only needs log2(size of list) queries to find the correct insertion position.

So, if your insert code was

void sortedInsert(List<T> list, T value, Comparator<T> comparator) {
  int pos=0;
  ListIterator<T> it=list.listIterator();
  while (it.hasNext() && comparator.compare(value, it.next()) < 0) pos ++;
  if (pos < it.previousIndex()) it.previous();
  it.add(value);
}

... and a faster version would be ...

void sortedInsert2(List<T> list, T value, Comparator<T> comparator) {
  int pos = Collections.binarySearch(list, value, comparator);
  if (pos < 0) {
     pos = -pos -1; // returns negatives if not found; see javadoc
  }
  list.insert(value, pos);
}

Note that the difference may not be that great, because inserting into a non-linked list requires shifting elements up. So if the underlying list is an ArrayList, copying, on average, half the elements one place to the right to make place for the new element results in O(n) extra time per copy. And if the list is linked, you still need to pay that O(n) penalty, but this time to perform the binary search -- in that case, it would probably be better to use the first version.

Note that the 1st version uses a ListIterator just in case you decide to use linked lists. For ArrayLists, it would be easier to use list.get(pos) and list.add(pos, value), but those are a very bad idea in the context of iterating linked lists.

It should be `int pos = -Collections.binarySearch(list, value, comparator) - 1;` (see the doc) or, equivalently, `~Collections.binarySearch(list, value, comparator)` (since `~x == -x - 1`). And only if duplicates are not allowed. — DodgyCodeException, Nov 13 '18 at 17:34
@DodgyCodeException you are entirely correct. I have fixed it for both cases (duplicates, where it now inserts before the 1st occurrence, and not-founds) — tucuxi, Nov 14 '18 at 11:31
It would be useful to also have a custom remove method as well. Otherwise, the standard List remove method would iterate through each element in turn until it finds one that is equal to the given element and remove it. That's an O(N) operation whereas a binary-search remove would be O(log N). @AfonsoMatos — DodgyCodeException, Nov 14 '18 at 12:43

score 1 · Answer 2 · answered Nov 13 '18 at 16:48

Can't you add the object in the "right" place? already sorted?

You said that every time you add a new object you sort the list/collection.

Maybe you can use a Binary Search to find the exact index you need to insert the new value or use your comparator to find.

Sorting a list from the beginning

2 Answers2