CODEWITHSUNDEEP
performance
I3i0
I3i0

Reputation: 1191

Sorting an array

I want to know which is better to sort an array of elements.

Is it better to get good performance to sort the array at the end when I finish filling it? Or it is better to sort it each time I add an element to it?

Upvotes: 0

Views: 144

Answers (2)

Travis Addair
Travis Addair

Reputation: 427

Ignoring the application-specific information for a moment, consider that sorted insertion requires, worst case, O(n) operations for each element. For n elements, this of course gives us O(n^2). If this sounds familiar, it's because what you're doing is (as another commenter pointed out) an insertion sort. In contrast, performing one quicksort on the entire list will take, worse case, O(n log n) time.

So, does this mean you should definitely wait until the end to sort? No. The important thing to remember is that O(n log n) is the best we can do for sorting in the general case. Your application-speciifc knowledge of the data can influence the best algorithm for the job. For example, if you know your data is already almost sorted, then insertion sort will give you linear time complexity.

Your mileage may vary, but I think the algorithmic viewpoint is useful when examining the general problem of "When should I sort?"

Upvotes: 1

ApplePie
ApplePie

Reputation: 8942

It depends on what is critical to you. Do you need to be able to insert very fast (a lot of entries but little queries) or do you need to be able to query very fast and insert slowly (a lot of queries but not many entries) ?

This is basically your problem to solve. When you know this you can select an appropriate sorting algorithm and apply it.

Edit: This is assuming that either choice actually matters. This depends a lot on your activity (inserts vs queries) and the amount of data that you need to sort.

Upvotes: 1

Related Questions