CODEWITHSUNDEEP
algorithmsorting
mr.abdo
mr.abdo

Reputation: 485

What is the most efficient algorithm to Insert an element in a ordered simple list

Which one is the best algorithm to insert a new element in a ordered list? Supose that I a have the list [1,3,8,10,14,20] and I'd like to insert the element 9.

I'm not talking about a programming language but about the most efficient algorithm to do that.

Tks

ps.: I'm not sure if the insert sort is the best one.

Upvotes: 1

Views: 2948

Answers (2)

user8401765
user8401765

Reputation:

Inserting a new element will take approximately the same time no matter the algorithm if its an array. To explain it better:

You will always need a O(n) complexity part in the algorithm to shift the array elements that come after the inserted element to make space where you can put that element.

Your best bet would be to decrease the search complexity, and the best way is to use binary search, which has a complexity of O(log n).

With this your insert has a complexity of (n + log n), which is the same as O(n).

To increase efficiency, you need to pick a better data structure, that has constant insert time like a binary search tree or a some sort of heap.

Upvotes: 1

Henry
Henry

Reputation: 43758

To insert a single element, you traverse the list from the front until you find the insertion point and then insert the new element (by pointer manipulations).

If you need to insert many elements and the list does not necessarily have to be sorted all the time it may be better to insert the new elements in the front and then do a final sort.

Upvotes: 2

Related Questions