Sorting Algorithms Optimisation Python

Question

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?

Answer 1

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.

Answer 2

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