[RESOLVED] Which one is more efficient in terms of collection sorting?

[oceanebelle]

for example, using the following:

the collection Set and sorting as we go.

Set sortedObject= new TreeSet<SomeObject>(comparator);

or

the collection list and sorting when all elements are in the list.

Collections.sort(list, comparator);

what are the adv and disadv in terms of memory usage and execution time?

[ComputerJy]

A TreeSet is a List. so if you want a comparison, you might want to be a bit more specific, whether you're talking about ArrayLists or LinkedLists.

Anyway, the implementation of the TreeSet provides a guaranteed log(n) time cost for the basic operations (add, remove and contains). Whilst the ArrayList would cost 1 for those operations (Unless array size was insufficient).

The Collections.sort uses the QuickSort algorithm which has the O(n log(n))

To wrap it all up, if you want your Items sorted all the time use the TreeSet. But if you only need the results sorted once, you might want to consider either an ArrayList or a LinkedList.

The LinkedList comes in handy if you have no idea what is the number of Items in your list. Because the ArrayList initializes an array for your data, and when full, initializes a new one and copies the old 1 inside it.. So it might be time wasting

[oceanebelle]

A TreeSet is a List. so if you want a comparison, you might want to be a bit more specific, whether you're talking about ArrayLists or LinkedLists.

Anyway, the implementation of the TreeSet provides a guaranteed log(n) time cost for the basic operations (add, remove and contains). Whilst the ArrayList would cost 1 for those operations (Unless array size was insufficient).

The Collections.sort uses the QuickSort algorithm which has the O(n log(n))

To wrap it all up, if you want your Items sorted all the time use the TreeSet. But if you only need the results sorted once, you might want to consider either an ArrayList or a LinkedList.

The LinkedList comes in handy if you have no idea what is the number of Items in your list. Because the ArrayList initializes an array for your data, and when full, initializes a new one and copies the old 1 inside it.. So it might be time wasting

Thanks for the reply, basically i was having problems with collections.sort() because I have a really big list and when sort() is called memory is insufficient due to the copying of the entire collection elements into an array to do the quicksort.

I was looking more into possible ways of minimizing memory usage without sacrificing too much performance.

Although now it's been decided to limit the number of elements on the list so my question might be irrelevant, but It's nice to know all the small stuff.

Anyways, most people use ArrayList(probably?), would it be a good practice to use LinkedList for like unknown number of elements?

Also, I like to use the Sorted variety, TreeSet and TreeMap for in place sorting as I go. When would it be a good idea to use the Sorted Collections and/or Collections.sort()?

[ComputerJy]

Anyways, most people use ArrayList(probably?), would it be a good practice to use LinkedList for like unknown number of elements?

Sure. Because an ArrayList holds all the data in a regular array. So when this array is full, it'll recreate the array with a larger size and copy the old array's data into the new array. Which is both time and memory wasting. Not only that but also an array need all it's elements to be in sequence in the physical memory. So creating new arrays will also need memory defragmentation in order to have that block of free memory. which you may not always have.

Also, I like to use the Sorted variety, TreeSet and TreeMap for in place sorting as I go. When would it be a good idea to use the Sorted Collections and/or Collections.sort()?

If you need your data sorted all the time, using the sorted collections would be a better idea (that's what they're for).

[oceanebelle]

Good stuff. Thanks

I guess for most people it's a matter of preference but in some cases these things do matter. Which collections to use and in what situation.