1

Which of the following two methods would be the faster one of keeping an ArrayList sorted ?

  • Inserting the element in its place
  • Calling push, then call Collections.sort(myList)
rares985
  • 341
  • 3
  • 15
  • 2
    Depending on what you are using it for, [`SortedSet`](https://docs.oracle.com/javase/8/docs/api/java/util/SortedSet.html) ? – khelwood Oct 19 '15 at 15:27
  • I want to have a list of Users(which is a separate class) whose ids must be in ascending order.Here I used Integer as an example in order not to complicate the question – rares985 Oct 19 '15 at 15:33
  • I think the answer from smonff is the one that makes the most sense: do not build your interfaces around fixed data structures. Instead, select that data structure that gives you what you need; without building additional layers around it. – GhostCat Oct 19 '15 at 15:36
  • I am kind of new to Java and it was the best approach I could think of.Thank you for your answer – rares985 Oct 19 '15 at 15:39

3 Answers3

3

There is different kinds of collections. You could choose one that keeps your data sorted.

smonff
  • 3,399
  • 3
  • 36
  • 46
2

It would probably be more efficient to insert in the right position, for example by using Collections.binarySearch(list, elementToInsert):

int index = Collections.binarySearch(list, element);
if (index < 0) index = - (index + 1);
list.add(index, element);

If you don't need random access and your entries are unique (which seems to be the case based on your comment), you could also use a TreeSet:

NaivigableSet<User> users = new TreeSet<> (Comparator.comparing(User::getId));

The set will always be sorted based on the user ids which must be unique.

assylias
  • 321,522
  • 82
  • 660
  • 783
  • If I will be using your method, my `User` class will have to implement `Comparable` and `Comparator`, right? – rares985 Oct 19 '15 at 16:04
  • @gusteru In the first example yes, although you can provide your own comparator if required: `Collections.binarySearch(list, element, Comparator.comparing(User::getId))`. In my second example I have already provided a comparator based on ids so no need for User to be Comparable in that case. – assylias Oct 19 '15 at 16:10
0

If your requirement asks for a continuous sorting after every insert, i think you should try alternate approach than the current one as this in itself is not time efficient. For a elaborate explanation for possible solution you must look at Sorted array list in Java

Community
  • 1
  • 1
pradex
  • 328
  • 4
  • 18