Mixing
What is the most efficient algorithm to Insert an element in a ordered simple list
up vote
0
down vote
favorite
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.
algorithm sorting
asked 23 hours ago
mr.abdo
54
add a comment |
up vote
0
down vote
favorite
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.
algorithm sorting
asked 23 hours ago
mr.abdo
54
List or array? These are different things.
– Henry
23 hours ago
@Henry list. I edited. Tks
– mr.abdo
23 hours ago
Well, you can use a doubly linked list. This way you won't have to shift elements.
– vivek_23
22 hours ago
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
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.
algorithm sorting
asked 23 hours ago
mr.abdo
54
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.
algorithm sorting
algorithm sorting
asked 23 hours ago
mr.abdo
54
asked 23 hours ago
mr.abdo
54
edited 23 hours ago
asked 23 hours ago
mr.abdo
54
asked 23 hours ago
mr.abdo
54
asked 23 hours ago
mr.abdo
54
54
List or array? These are different things.
– Henry
23 hours ago
@Henry list. I edited. Tks
– mr.abdo
23 hours ago
Well, you can use a doubly linked list. This way you won't have to shift elements.
– vivek_23
22 hours ago
add a comment |
List or array? These are different things.
– Henry
23 hours ago
@Henry list. I edited. Tks
– mr.abdo
23 hours ago
Well, you can use a doubly linked list. This way you won't have to shift elements.
– vivek_23
22 hours ago
List or array? These are different things.
– Henry
23 hours ago
List or array? These are different things.
– Henry
23 hours ago
@Henry list. I edited. Tks
– mr.abdo
23 hours ago
@Henry list. I edited. Tks
– mr.abdo
23 hours ago
Well, you can use a doubly linked list. This way you won't have to shift elements.
– vivek_23
22 hours ago
Well, you can use a doubly linked list. This way you won't have to shift elements.
– vivek_23
22 hours ago
add a comment |
2 Answers
2
active
oldest
votes
up vote
2
down vote
accepted
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.
answered 23 hours ago
Henry
32.8k54259
add a comment |
up vote
0
down vote
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.
answered 23 hours ago
nihilist_banana
15911
1
The question is about a list, but apart from that the complexity of binary search is not needed. One can combine shifting up with the search.
– Henry
23 hours ago
If it's a list, then you are right. Also, in that case, we cant use binary search. But I still stand by the bold part.
– nihilist_banana
23 hours ago
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
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.
answered 23 hours ago
Henry
32.8k54259
add a comment |
up vote
2
down vote
accepted
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.
answered 23 hours ago
Henry
32.8k54259
add a comment |
up vote
2
down vote
accepted
up vote
2
down vote
accepted
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.
answered 23 hours ago
Henry
32.8k54259
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.
answered 23 hours ago
Henry
32.8k54259
answered 23 hours ago
Henry
32.8k54259
answered 23 hours ago
Henry
32.8k54259
answered 23 hours ago
Henry
32.8k54259
32.8k54259
add a comment |
add a comment |
up vote
0
down vote
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.
answered 23 hours ago
nihilist_banana
15911
1
The question is about a list, but apart from that the complexity of binary search is not needed. One can combine shifting up with the search.
– Henry
23 hours ago
If it's a list, then you are right. Also, in that case, we cant use binary search. But I still stand by the bold part.
– nihilist_banana
23 hours ago
add a comment |
up vote
0
down vote
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.
answered 23 hours ago
nihilist_banana
15911
1
The question is about a list, but apart from that the complexity of binary search is not needed. One can combine shifting up with the search.
– Henry
23 hours ago
If it's a list, then you are right. Also, in that case, we cant use binary search. But I still stand by the bold part.
– nihilist_banana
23 hours ago
add a comment |
up vote
0
down vote
up vote
0
down vote
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.
answered 23 hours ago
nihilist_banana
15911
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.
answered 23 hours ago
nihilist_banana
15911
answered 23 hours ago
nihilist_banana
15911
answered 23 hours ago
nihilist_banana
15911
answered 23 hours ago
nihilist_banana
15911
15911
1
The question is about a list, but apart from that the complexity of binary search is not needed. One can combine shifting up with the search.
– Henry
23 hours ago
If it's a list, then you are right. Also, in that case, we cant use binary search. But I still stand by the bold part.
– nihilist_banana
23 hours ago
add a comment |
1
The question is about a list, but apart from that the complexity of binary search is not needed. One can combine shifting up with the search.
– Henry
23 hours ago
If it's a list, then you are right. Also, in that case, we cant use binary search. But I still stand by the bold part.
– nihilist_banana
23 hours ago
1
1
The question is about a list, but apart from that the complexity of binary search is not needed. One can combine shifting up with the search.
– Henry
23 hours ago
The question is about a list, but apart from that the complexity of binary search is not needed. One can combine shifting up with the search.
– Henry
23 hours ago
If it's a list, then you are right. Also, in that case, we cant use binary search. But I still stand by the bold part.
– nihilist_banana
23 hours ago
If it's a list, then you are right. Also, in that case, we cant use binary search. But I still stand by the bold part.
– nihilist_banana
23 hours ago
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53372159%2fwhat-is-the-most-efficient-algorithm-to-insert-an-element-in-a-ordered-simple-li%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
List or array? These are different things.
– Henry
23 hours ago
@Henry list. I edited. Tks
– mr.abdo
23 hours ago
Well, you can use a doubly linked list. This way you won't have to shift elements.
– vivek_23
22 hours ago