Finding the minimum number of swaps to sort a list

Question

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
  while first<=last and not found:
    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!

Answer 1

1. It's accidentally quadratic

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))