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

def no_swap(a):
  for i in range(n):
    if a[i]!=sorted_a[i]:

    if rev_a[i]!=sorted_a[i]:

  return min(noswap1,noswap2)

def swaplist(i,j,arr):
  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
      if item < alist[midpoint]:
       last = midpoint-1
        first = midpoint+1

  return midpoint

Any suggestions are appreciated!

  • \$\begingroup\$ 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. \$\endgroup\$
    – Graipher
    Commented Aug 4, 2017 at 9:38
  • \$\begingroup\$ Can you update the post to add the code for binarySearch, please? Also, could you correct the indentation error in the swaplist function? \$\endgroup\$ Commented Aug 4, 2017 at 9:55
  • 1
    \$\begingroup\$ @GarethRees done! \$\endgroup\$
    – n0unc3
    Commented Aug 4, 2017 at 10:20

1 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


    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:

4815936072 being sorted to 0123456789

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

4815936072 being sorted, as a 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.

4815936072 being sorted, decomposed into cycles 6, 35, 4921870

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:
        yield cycle

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

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

    permutation = sorted(range(len(seq)), key=seq.__getitem__)
    return sum(len(cycle) - 1 for cycle in cycle_decomposition(permutation))
  • \$\begingroup\$ This also works for Sequence[float]. As an aside, I was able to get a 35% speedup by using Cython. \$\endgroup\$
    – Asclepius
    Commented Jan 16, 2022 at 1:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.