Your code is \$O(n^2)\$ because of the inner loop.
for j in range(i+1,len(Queue)): if Queue[j] == i+1: # inner
We can change this to be \$O(1)\$ by making a lookup table of where \$i\$'s location is. We can build a dictionary to store these lookups.
indexes = {value: index for index, value in enumerate(Queue)
We can then just swap these indexes with your existing inner code to get \$O(n)\$ performance.
def MinimumSwaps(Queue):
indexes = {value: index for index, value in enumerate(Queue)}
MinSwaps = 0
for i in range(len(Queue) - 1):
i_value = Queue[i]
if i_value != i+1:
j = indexes[i+1]
j_value = Queue[j]
Queue[i], Queue[j] = Queue[j], Queue[i]
indexes[i_value], indexes[j_value] = indexes[j_value], indexes[i_value]
MinSwaps += 1
else:
continue
return MinSwaps
There is potentially performance on the table by using a dictionary as a lookup table rather than a list. Whilst both have the same algorithmic complexity. To address this we can just build indexes
as a list.
indexes = [None] * len(Queue)
for index, value in enumerate(Queue):
indexes[value] = index