# Finding the minimum number of swaps to sort a list

I can handle large numbers with this code as well but I need to improve my execution time.

def no_swap(a):
sorted_a=sorted(a)
rev_a=list(reversed(a))
b=a[:]
n=len(a)
noswap1=0
noswap2=0
for i in range(n):
if a[i]!=sorted_a[i]:
noswap1=noswap1+1
j=binarySearch(sorted_a[i],a)
a=swaplist(i,j,a)

if rev_a[i]!=sorted_a[i]:
noswap2=noswap2+1
j=binarySearch(sorted_a[i],rev_a)
b=swaplist(i,j,rev_a)

return min(noswap1,noswap2)

def swaplist(i,j,arr):
temp=arr[i]
arr[i]=arr[j]
arr[j]=temp
return arr

def binarySearch(item, alist):
first = 0
last = len(alist)-1
found = False
midpoint = (first + last)
if alist[midpoint] == item:
found = True
else:
if item < alist[midpoint]:
last = midpoint-1
else:
first = midpoint+1

return midpoint


Any suggestions are appreciated!

• Hey, welcome to Code Revew! Asking about improvements is the default for any question here, so there is no need to ask for it in the question title. I reduced your title to what your code actually does. You might want to take a look at our How do I ask a good question? page and take our tour. – Graipher Aug 4 '17 at 9:38
• Can you update the post to add the code for binarySearch, please? Also, could you correct the indentation error in the swaplist function? – Gareth Rees Aug 4 '17 at 9:55
• @GarethRees done! – n0unc3 Aug 4 '17 at 10:20

The line:

midpoint = (first + last)


should be:

midpoint = (first + last) // 2


The consequence of this mistake is that binarySearch takes $Θ(n)$ to find the location, instead of the intended $O(\log n)$. And binarySearch is called for every item in the list, making the overall runtime $Θ(n^2)$ instead of the intended $O(n \log n)$.

### 2. Review of binarySearch

1. There's no docstring. What does it do? What arguments do I pass? What does it return?

2. The Python style guide (PEP8) recommends:

4 spaces per indentation level

and:

Always surround these binary operators with a single space on either side: [...] comparisons (<=), [...]

Following PEP8 will make it easier for you to collaborate with other Python programmers.

3. A local variable found is used to exit the while loop. But Python's break statement also exits a loop, and if you used this you'd avoid the need for the variable.

4. else: if can be written elif:, saving a level of indentation.

5. Consider using the built-in bisect module.

### 3. Alternative approach

The rearrangement of items that happens when you sort a list is known as a permutation. For example, let's take this list of items:

When we sort the list, each item moves to a new position in the list, shown by the arrows:

We can draw the same arrows on a single row of items, showing where each item goes in the permutation:

The structure of the permutation becomes clear if we rearrange the items so that none of the arrows are crossing. Every permutation consists of one or more cycles: in this case there is a 1-cycle sending 6 to itself, a 2-cycle swapping 3 and 5, and a 7-cycle sending 4 to 9 to 2 to 1 to 8 to 7 to 0 to 4.

It takes $n-1$ swaps to implement a cycle of length $n$. So if the sorted permutation of a list can be decomposed into cycles with lengths $a, b, c, \ldots, z$ then the minimum number of swaps needed to sort the list is $(a - 1) + (b - 1) + (c - 1) + \cdots + (z - 1)$.

Here's an implementation that finds the cycles first and then uses their lengths to count the swaps. (It's not actually necessary to find the cycles, you could just count the swaps as you go along, but I think this is clearer to begin with.)

def cycle_decomposition(permutation):
"""Generate cycles in the cyclic decomposition of a permutation.

>>> list(cycle_decomposition([7, 2, 9, 5, 0, 3, 6, 8, 1, 4]))
[[0, 7, 8, 1, 2, 9, 4], [3, 5], [6]]

"""
unvisited = set(permutation)
while unvisited:
j = i = unvisited.pop()
cycle = [i]
while True:
j = permutation[j]
if j == i:
break
cycle.append(j)
unvisited.remove(j)
yield cycle

def minimum_swaps(seq):
"""Return minimum swaps needed to sort the sequence.

>>> minimum_swaps([])
0
>>> minimum_swaps([2, 1])
1
>>> minimum_swaps([4, 8, 1, 5, 9, 3, 6, 0, 7, 2])
7

"""
permutation = sorted(range(len(seq)), key=seq.__getitem__)
return sum(len(cycle) - 1 for cycle in cycle_decomposition(permutation))