Most efficient way to sort an array while inserting elements?

Question

So i have an array, and every time I add an element I need to put that element in its proper place, then shift the array to make room for the new element. Most efficient way to do this?

Answer 1

If u r use ing java, TreeSet is the best.

Answer 2

An efficient way is to do a binary search to find the right position, then shift the array and after that you insert cus if you insert and then shift, you will lose an element in the array.



A binary search is:

You look at the middle of the array and compare the element there with the one you want to insert. If they R equal, then you found your position, else if the middle is bigger than you item you take the lower half of the array and repeat the search . Else if it is smaller than you item you take the higher half of the array and repeat the process. In every iteration you need to have a special condition for when you array has only one item and that's it.



This can vary depending on your problem specs Ex: if you allow duplicates in the array or not. But that's more or less the idea.

Answer 3

Check out Insertion Sort from this search:

http://search.yahoo.com/search?p=insert+sort



Binary search here:

http://search.yahoo.com/search?p=binary+search



Quick sort here:

http://search.yahoo.com/search?p=quick+sort



Then determine which is the best for you and your application.