CODEWITHSUNDEEP
performancelistsorting
Decko
Decko

Reputation: 19375

Should you sort a list when getting or setting it?

A decision I often run into is when to sort a list of items. When an item is added, keeping the list sorted at all times, or when the list is accessed.

Is there a best practice for better performance, or is it just the matter of saying: if the list is mostly accessed, sort it when it is changed or vice versa.

Upvotes: 1

Views: 145

Answers (3)

digEmAll
digEmAll

Reputation: 57220

I'm used to think in this way:

  • If the list is filled all at once and only after this is read, then add elements in non-sorted order and sort it just at the end of filling (in complexity terms it requires O(n log n) plus the complexity of filling, and that's usually faster than sorting while adding elements)
  • Conversely, if the list needs to be read before it is completely filled, then you have to add elements in sorted order (maybe using some special data structure doing the work for you, like sortedlist, red-black tree etc.)

Upvotes: 1

codymanix
codymanix

Reputation: 29520

Sorting the list at every acccess is a bad idea. You have to have a flag which you set when the collection is modified. Only if this flag is set, you need to sort and then reset the flag.

But the best is if you have a data structure which is per definition always sorted. That means, if you insert a new element, the element is automatically inserted at the right index, thus keeping the collection sorted.

I don't know which platform / framework you are using. I know .NET provides a SortedList class which manages that kind of insertion-sort algorithm for you.

Upvotes: 1

vlg789
vlg789

Reputation: 751

The answer is a big depends. You should profile and apply a strategy that is best for your case.

If you want performance on access/finding elements a good decision will be to maintain the list sorted using InsertionSort (http://en.wikipedia.org/wiki/Insertion_sort).

Sorting list on access may be an option only on some very particular scenarios, when are many insertions, low access and performance is not very important.

But, there are many other options: like maintain a var that say "list is sorted" and sort at every n-th insertion, on idle or on access (if you need).

Upvotes: 1

Related Questions