How to Find Minimum Swaps to Sort an Array in Python

Calculate the minimum number of adjacent-free swaps needed to sort a permutation array using cycle detection in Python.

Medium Python 3.9+ Aug 9, 2026 Algorithms & data structures 13 views 0 copies

sorting cycles greedy permutation algorithm

Python code

31 lines

Python 3.9+

def min_swaps_to_sort(arr):
    n = len(arr)
    arr_pos = sorted((val, idx) for idx, val in enumerate(arr))
    visited = [False] * n
    swaps = 0

    for i in range(n):
        if visited[i] or arr_pos[i][1] == i:
            continue

        cycle_size = 0
        j = i
        while not visited[j]:
            visited[j] = True
            j = arr_pos[j][1]
            cycle_size += 1

        if cycle_size > 0:
            swaps += cycle_size - 1

    return swaps


if __name__ == "__main__":
    test_array = [4, 3, 2, 1]
    result = min_swaps_to_sort(test_array)
    print(f"Minimum swaps to sort {test_array}: {result}")

    test_array2 = [1, 5, 4, 3, 2]
    result2 = min_swaps_to_sort(test_array2)
    print(f"Minimum swaps to sort {test_array2}: {result2}")

Output

stdout

Minimum swaps to sort [4, 3, 2, 1]: 2
Minimum swaps to sort [1, 5, 4, 3, 2]: 3

How it works

The algorithm works by sorting the array values with their original indices to determine where each element should be after sorting. Each index forms a cycle where following the target positions eventually returns to the start. For a cycle of length k, only k-1 swaps are needed to place all elements in their correct positions. The visited array prevents recounting the same cycle multiple times. Summing the (cycle_size - 1) across all cycles gives the total minimum swaps required.

Common mistakes

Assuming you can swap adjacent elements only, which changes the problem to counting inversions
Forgetting to mark visited nodes, leading to double-counting the same cycle
Handling duplicate values incorrectly, which may require a more complex matching strategy

Variations

Use a dictionary to map each value to its target index for O(1) lookups instead of sorting tuples
For arrays with duplicates, use a queue-based approach to handle ambiguous target positions

Real-world use cases

Minimizing the number of file reorder operations when sorting records in a database migration.
Computing the minimal number of moves to arrange a puzzle or game board permutation.
Optimizing swap costs in distributed storage when rebalancing data across nodes based on sorted keys.

How to Find Minimum Swaps to Sort an Array in Python

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Algorithms & data structures

Tutorials

Quizzes

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Algorithms & data structures

Keep learning

Tutorials

Quizzes