What basic algorithm to choose for build sorted list? And how to get best perfomance durring adding to sorted list?

Question

For exmple, i have undefined number of a pairs(key, value). And I want to build sorted list during iterate trough this pairs(it is long operation).

I think to use a BinaryTree as a sorted structure and build list from tree after iterations.

How you think in generally, is this method faster than simple sorting of the list getted from iterate trough the pairs?

What the best way to resolve this issue?

Is some java API items for this issue?

Answer 1

In C++ the STL's performance might be good enough for an initial implementation - avoiding "premature optimization" -- assuming you're on a single thread, otherwise I always recommend Duffy's "Concurrent Programming on Windows".

Answer 2

You can throw them all into a TreeMap, and let Java handle the sorting. Then you can iterate over the map, and you will get your keys in their sorted order.

Answer 3

How you think in generally, is this method faster than simple sorting of the list getted from iterate trough the pairs?

No. If the sorting and the tree are implemented correctly, the complexity of both is identical: O(n*log(n)). For the constant factors, best do some benchmarks yourself. The tree will probably require more memory, at least compared to an in-place sorting algorithm like quicksort.

Java APIs:

• java.util.TreeMap for the tree
• java.util.Collections.sort() for the sorting

Answer 4

If you absolutely need to use a list you can use Collections.binarySearch to determine the proper insertion point for adding a new element to the list, thus maintaining sorted order without actually requiring any sorting operations.