CODEWITHSUNDEEP
java
user705414
user705414

Reputation: 21200

I have a list of integers , how to sort it?

Have a list of integers like

List<Integer> l = new ArrayList<Integer>();

I think calling l.contains is slow, how to sort the list. After sorting, will l.contains behave faster?

Is there any sortedList I can use directly?

Upvotes: 3

Views: 339

Answers (7)

Mairbek Khadikov
Mairbek Khadikov

Reputation: 8089

Sorting of list would not make contains operation faster. It still be O(n) in worst case.

However you can sort your list and perform the binary search on top of it.

Collections.sort(l);
Collections.binarySearch(l, a);

This will take O(lg(n)) time in worst case.

But if you want a high performance contains operation consider using HashSet instead of ArrayList. It takes nearly constant time.

Upvotes: 6

DwB
DwB

Reputation: 38300

If Collections.sort(l) does not give the desired result, try Collections.sort(l, comparator) where "comparator" is something like this:

class MyComparator implements Comparator<Integer>
{
  public int compare(Integer lhs, Integer rhs)
  {
    // perform the desired comparison.
  }
}

Edit: I'll leave this up, but the answer by "Mairbek Khadikov" seems to be the best answer.

Upvotes: 0

e-zinc
e-zinc

Reputation: 4581

TreeSet may be useful for you. 

SortedSet<Integer> s = new TreeSet<Integer>(l);

Upvotes: 0

talnicolas
talnicolas

Reputation: 14053

The sort() method from Collections can help you sort your ArrayList.

Upvotes: 2

user684934
user684934

Reputation:

contains() on a ArrayList doesn't assume the array is sorted, even if it is. You'll want to use some sort of set (HashSet will give you the best find performance, and a LinkedHashSet will retain the order. Even a TreeList will give you better performance.)

Upvotes: 1

fmucar
fmucar

Reputation: 14548

You can use Collections.sort(l);

Upvotes: 4

adarshr
adarshr

Reputation: 62573

It can't get simpler than this.

Collections.sort(l);

Upvotes: 13

Related Questions