# Sorting Algorithms Optimisation Python

def MinimumSwaps(Queue):
MinSwaps = 0
for i in range(len(Queue) - 1):
if Queue[i] != i+1:
for j in range(i+1,len(Queue)):
if Queue[j] == i+1:
Queue[i], Queue[j] = Queue[j], Queue[i]
MinSwaps += 1
break
else:
continue
return MinSwaps

def main():
Result = MinimumSwaps([7, 1, 3, 2, 4, 5, 6])
print(Result)
if __name__ == "__main__":
main()


The question: You are given an unordered array consisting of consecutive integers [1, 2, 3, ..., n] without any duplicates. You are allowed to swap any two elements. You need to find the minimum number of swaps required to sort the array in ascending order.

The issue is that what I have provided is inefficient and fails on very large arrays, however Ive tried to optimise it as much as I can and im not aware of another technique to use. This question is likely related to a particular sorting algorithm but is there any way to modify the above code to make it faster?

• how large is n? Commented Feb 18, 2021 at 17:14
• 100,000 is the max.
– Jack
Commented Feb 18, 2021 at 17:30
• Unordered array of consecutives..?
– DT1
Commented Feb 18, 2021 at 17:34
• Yes, just consider it a randomised array of integers that were originally consecutive. But it was described as I posted in the question. An example is given in the main() function.
– Jack
Commented Feb 18, 2021 at 17:40
• Is the input a Queue?
– tsh
Commented Feb 19, 2021 at 6:16

Instead of searching for the value that belongs at Queue[i] to swap it there, just swap the value that is there to where that belongs:

def MinimumSwaps(Queue):
MinSwaps = 0
for i in range(len(Queue) - 1):
while Queue[i] != i + 1:
j = Queue[i] - 1
Queue[i], Queue[j] = Queue[j], Queue[i]
MinSwaps += 1
return MinSwaps


This improves the performance to $$\O(1)\$$ for using a value instead of the $$\O(n)\$$ for searching. And thus total performance to $$\O(n)\$$ instead of your original $$\O(n^2)\$$. Still using only O(1) extra space.

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

• Why this answer get downvoted? It may not be the best idea. But it at least works (boost the performance by reducing the big-O time complexity of original code).
– tsh
Commented Feb 19, 2021 at 6:21
• @tsh Another user has taken a quite unhealthy dislike to me. So downvoted straight after seeing who posted the answer. The second, IDK. As you say the answer answered the question by improving the performance of the code, could my answer be poorly worded or something? IDK. Speculating probably isn't a good idea unless I get a couple more downvotes. So in the mean time I'll just assume Tim lost his keys again. Commented Feb 19, 2021 at 12:07
• @tsh I see the OP's way as going in the wrong direction (solving towards the current list spot instead of the simpler and faster away from the current list spot) and thus this solution as running in the wrong direction, with even more complicated code and less space-efficiency. Plus just recently they made a fuss about set operations being O(n) instead of O(1), which they then should've done here for the dict as well. Commented Feb 19, 2021 at 13:16
• @superbrain "which they then should've done here" I did, look at the bottom of the post. Commented Feb 19, 2021 at 13:17
• Where? You even explicitly say "We can change this to be O(1)". Commented Feb 19, 2021 at 13:18