Inserting an integer into a sorted list
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
I'm wondering if inserting an integer into a sorted list (in a way that the list remains sorted) can be performed in Mathematica in some fancy way in $log(N)$ time?..
The question was asked here, but I'm not sure if any of realizations presented there work in $log(N)$. I would appreciate if anyone provided the solution for not simply a list, but for a list of lists sorted by their certain element. E.g.:
ins[1,b,3,,14,"hi!",6,0]
gives:
1,b,3,,6,0,14,"hi!"
Where sorting was performed by the first field of the sublist.
list-manipulation sorting
asked 2 hours ago
mavzolej
35819
add a comment |Â
up vote
2
down vote
favorite
I'm wondering if inserting an integer into a sorted list (in a way that the list remains sorted) can be performed in Mathematica in some fancy way in $log(N)$ time?..
The question was asked here, but I'm not sure if any of realizations presented there work in $log(N)$. I would appreciate if anyone provided the solution for not simply a list, but for a list of lists sorted by their certain element. E.g.:
ins[1,b,3,,14,"hi!",6,0]
gives:
1,b,3,,6,0,14,"hi!"
Where sorting was performed by the first field of the sublist.
list-manipulation sorting
asked 2 hours ago
mavzolej
35819
1
Of course, one could implement a binary tree...
– Henrik Schumacher
1 hour ago
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
I'm wondering if inserting an integer into a sorted list (in a way that the list remains sorted) can be performed in Mathematica in some fancy way in $log(N)$ time?..
The question was asked here, but I'm not sure if any of realizations presented there work in $log(N)$. I would appreciate if anyone provided the solution for not simply a list, but for a list of lists sorted by their certain element. E.g.:
ins[1,b,3,,14,"hi!",6,0]
gives:
1,b,3,,6,0,14,"hi!"
Where sorting was performed by the first field of the sublist.
list-manipulation sorting
asked 2 hours ago
mavzolej
35819
I'm wondering if inserting an integer into a sorted list (in a way that the list remains sorted) can be performed in Mathematica in some fancy way in $log(N)$ time?..
The question was asked here, but I'm not sure if any of realizations presented there work in $log(N)$. I would appreciate if anyone provided the solution for not simply a list, but for a list of lists sorted by their certain element. E.g.:
ins[1,b,3,,14,"hi!",6,0]
gives:
1,b,3,,6,0,14,"hi!"
Where sorting was performed by the first field of the sublist.
list-manipulation sorting
list-manipulation sorting
asked 2 hours ago
mavzolej
35819
asked 2 hours ago
mavzolej
35819
asked 2 hours ago
mavzolej
35819
asked 2 hours ago
mavzolej
35819
asked 2 hours ago
mavzolej
35819
35819
1
Of course, one could implement a binary tree...
– Henrik Schumacher
1 hour ago
add a comment |Â
1
Of course, one could implement a binary tree...
– Henrik Schumacher
1 hour ago
1
1
Of course, one could implement a binary tree...
– Henrik Schumacher
1 hour ago
Of course, one could implement a binary tree...
– Henrik Schumacher
1 hour ago
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
1
down vote
accepted
ClearAll[insertAndSort]
insertAndSort = With[a = Join[#, #2], a[[Ordering[a[[All, 1]]]]]] &;
Example:
a = 1, c, 3, , 14, "hi!";
b = 6, 0;
insertAndSort[a, b]
1, c, 3, , 6, 0, 14, "hi!"
x[[Ordering@x]] is much faster than Sort[x] for large lists.
answered 38 mins ago
kglr
169k8192396
Cool! This is probably exactly what I was looking for.
– mavzolej
5 mins ago
add a comment |Â
up vote
2
down vote
myList = 1, b, 3, , 14, "hi!";
myElement = 6, 0;
SortBy[Join[myList, myElement], First]
answered 1 hour ago
David G. Stork
22k21747
"How come I did not come up with this..."
– mavzolej
1 hour ago
@mavzolej: Sorry... THAT problem I simply cannot solve!
– David G. Stork
1 hour ago
I just forgot that Mathematica's built-in sorting algorithm is probably smart enough to work in at most $Nlog N$ time, while for a single unsorted element it should be able to work in $log N$.
– mavzolej
1 hour ago
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
ClearAll[insertAndSort]
insertAndSort = With[a = Join[#, #2], a[[Ordering[a[[All, 1]]]]]] &;
Example:
a = 1, c, 3, , 14, "hi!";
b = 6, 0;
insertAndSort[a, b]
1, c, 3, , 6, 0, 14, "hi!"
x[[Ordering@x]] is much faster than Sort[x] for large lists.
answered 38 mins ago
kglr
169k8192396
Cool! This is probably exactly what I was looking for.
– mavzolej
5 mins ago
add a comment |Â
up vote
1
down vote
accepted
ClearAll[insertAndSort]
insertAndSort = With[a = Join[#, #2], a[[Ordering[a[[All, 1]]]]]] &;
Example:
a = 1, c, 3, , 14, "hi!";
b = 6, 0;
insertAndSort[a, b]
1, c, 3, , 6, 0, 14, "hi!"
x[[Ordering@x]] is much faster than Sort[x] for large lists.
answered 38 mins ago
kglr
169k8192396
Cool! This is probably exactly what I was looking for.
– mavzolej
5 mins ago
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
ClearAll[insertAndSort]
insertAndSort = With[a = Join[#, #2], a[[Ordering[a[[All, 1]]]]]] &;
Example:
a = 1, c, 3, , 14, "hi!";
b = 6, 0;
insertAndSort[a, b]
1, c, 3, , 6, 0, 14, "hi!"
x[[Ordering@x]] is much faster than Sort[x] for large lists.
answered 38 mins ago
kglr
169k8192396
ClearAll[insertAndSort]
insertAndSort = With[a = Join[#, #2], a[[Ordering[a[[All, 1]]]]]] &;
Example:
a = 1, c, 3, , 14, "hi!";
b = 6, 0;
insertAndSort[a, b]
1, c, 3, , 6, 0, 14, "hi!"
x[[Ordering@x]] is much faster than Sort[x] for large lists.
answered 38 mins ago
kglr
169k8192396
edited 23 mins ago
answered 38 mins ago
kglr
169k8192396
answered 38 mins ago
kglr
169k8192396
answered 38 mins ago
kglr
169k8192396
169k8192396
Cool! This is probably exactly what I was looking for.
– mavzolej
5 mins ago
add a comment |Â
Cool! This is probably exactly what I was looking for.
– mavzolej
5 mins ago
Cool! This is probably exactly what I was looking for.
– mavzolej
5 mins ago
Cool! This is probably exactly what I was looking for.
– mavzolej
5 mins ago
add a comment |Â
up vote
2
down vote
myList = 1, b, 3, , 14, "hi!";
myElement = 6, 0;
SortBy[Join[myList, myElement], First]
answered 1 hour ago
David G. Stork
22k21747
"How come I did not come up with this..."
– mavzolej
1 hour ago
@mavzolej: Sorry... THAT problem I simply cannot solve!
– David G. Stork
1 hour ago
I just forgot that Mathematica's built-in sorting algorithm is probably smart enough to work in at most $Nlog N$ time, while for a single unsorted element it should be able to work in $log N$.
– mavzolej
1 hour ago
add a comment |Â
up vote
2
down vote
myList = 1, b, 3, , 14, "hi!";
myElement = 6, 0;
SortBy[Join[myList, myElement], First]
answered 1 hour ago
David G. Stork
22k21747
"How come I did not come up with this..."
– mavzolej
1 hour ago
@mavzolej: Sorry... THAT problem I simply cannot solve!
– David G. Stork
1 hour ago
I just forgot that Mathematica's built-in sorting algorithm is probably smart enough to work in at most $Nlog N$ time, while for a single unsorted element it should be able to work in $log N$.
– mavzolej
1 hour ago
add a comment |Â
up vote
2
down vote
up vote
2
down vote
myList = 1, b, 3, , 14, "hi!";
myElement = 6, 0;
SortBy[Join[myList, myElement], First]
answered 1 hour ago
David G. Stork
22k21747
myList = 1, b, 3, , 14, "hi!";
myElement = 6, 0;
SortBy[Join[myList, myElement], First]
answered 1 hour ago
David G. Stork
22k21747
answered 1 hour ago
David G. Stork
22k21747
answered 1 hour ago
David G. Stork
22k21747
answered 1 hour ago
David G. Stork
22k21747
22k21747
"How come I did not come up with this..."
– mavzolej
1 hour ago
@mavzolej: Sorry... THAT problem I simply cannot solve!
– David G. Stork
1 hour ago
I just forgot that Mathematica's built-in sorting algorithm is probably smart enough to work in at most $Nlog N$ time, while for a single unsorted element it should be able to work in $log N$.
– mavzolej
1 hour ago
add a comment |Â
"How come I did not come up with this..."
– mavzolej
1 hour ago
@mavzolej: Sorry... THAT problem I simply cannot solve!
– David G. Stork
1 hour ago
I just forgot that Mathematica's built-in sorting algorithm is probably smart enough to work in at most $Nlog N$ time, while for a single unsorted element it should be able to work in $log N$.
– mavzolej
1 hour ago
"How come I did not come up with this..."
– mavzolej
1 hour ago
"How come I did not come up with this..."
– mavzolej
1 hour ago
@mavzolej: Sorry... THAT problem I simply cannot solve!
– David G. Stork
1 hour ago
@mavzolej: Sorry... THAT problem I simply cannot solve!
– David G. Stork
1 hour ago
I just forgot that Mathematica's built-in sorting algorithm is probably smart enough to work in at most $Nlog N$ time, while for a single unsorted element it should be able to work in $log N$.
– mavzolej
1 hour ago
I just forgot that Mathematica's built-in sorting algorithm is probably smart enough to work in at most $Nlog N$ time, while for a single unsorted element it should be able to work in $log N$.
– mavzolej
1 hour 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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathematica.stackexchange.com%2fquestions%2f185197%2finserting-an-integer-into-a-sorted-list%23new-answer', 'question_page');
);
Post as a guest
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
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
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
1
Of course, one could implement a binary tree...
– Henrik Schumacher
1 hour ago