How to change the position of an element in an array (list... in python)?

Question

Suppose I've a list and now I want to change the position of one of it's elements. For instance, I want to change the position of A[i] to j. How can I do it efficiently (with less runtime and memory)?
#if you are non-pythonistas then please share the algorithm

**not swapping
ex. [1,2,3,4,5] > [1,4,2,3,5] #moving 4 from position 3 to 1

**its INSERTION

**I've got one:
A.insert(j, A.pop(i)) #It is not an efficient approach, because pop is deleting an element, and reducing the size of the list, and again insert is adding an element, and increasing the size of list. So, the length of the array is changing for 2 times, and change of length is expensive for any type of array.

[Updated on March 5, 2021]

Hello everyone! For the last few days I was trying to solve the above problem in the fastest way possible. Here goes my implementation: https://code.sololearn.com/cr6MgZwo82P1/?ref=app . If anyone has got some other idea to solve the same, then please let us know. Thanks!

Answer 1

Till now this is the best approach:

def insert_n_to_i(A, i, n):
"""slice the list and change the order to bring the target to the new position"""
if i < n:
A[n], A[i:n] = A[i], A[i+1:n+1]
else:
A[n], A[n+1:i+1] = A[i], A[n:i]

If you know something better, then please reply here. Thanks!

Answer 2

Faheem Hossain , why are you thinking your code is non-efficient? Did you make some tries with measuring time complexity and memory consumption? And if yes, please show us the code you compared it with, and also the result of your measurement. Please also tell us on which system you ran that code like sololearn playground or local IDE. Thanks!

Answer 3

I guess you don't want swapping like this?

mylist = [1, 2, 3]
mylist[0], mylist[1] = mylist[1], mylist[0]
print(mylist) # [2, 1, 3]

https://code.sololearn.com/cNug95I9rG1u

Answer 4

Faheem Hossain , the code you provided does just a simple swapping. When you are looking for a way to do something as you mentiond in your last comment, you should try it by yourself first. Please present your code here that we can help you.
Please provide us with a clear sample of input and how this should looks like after applying some code. Thanks!

Answer 5

a[i],a[j]=a[j],a[i] i don't know it's inner workings but it takes less runtime than yours and I can't say anything about memory as well ,wait for others explanation:-)

Answer 6

Faheem Hossain , do you mean something like this:

input: [1,2,3,4,5,6]
output [1,[2,3],4,5,6]

Answer 7

Abhay
You are telling about swapping.
But its not swapping, i want to move ith element to j and move all elements inside i and j to one place right.
Thanks! I was wanting an algorithm which will do the above and be efficient like your one (swapping).

Answer 8

David Ashton
Lothar
Input : [1,2,3,4,5]
Let i = 3, j = 1
Output : [1,4,2,3,5]

My code :
A.insert(j, A.pop(i))
#i gave this in the question and i repeat that i dont know why, but its not that of a great use. I dont know its algorithm, but probably its running in a very bad runtime; please can you say why its bad and how i can increase its efficiency like one given by David Ashton 's one, but keeping the concept like one i exampled above.

Answer 9

Faheem Hossain , thanks for your information, now its a bit more clear. But again, i still feel a bit uncomfortable with your statement "running in a very bad runtime." As long as you can't show as a concrete measurement comparing with other algorithms it looks a bit dubious for me.

Answer 10

NotAPythonNinja
I don't know its insights. Although it works but i don't know why, causes a great runtime!

Answer 11

Yeah

Answer 12

David Ashton
Lothar
Thanks to everyone for your help! I hope this code will help you all to understand the problem clearly, and think of a better solution.
Code: https://code.sololearn.com/cr6MgZwo82P1/?ref=app