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!

  • 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
  • 1
    @GarethRees done! – n0unc3 Aug 4 '17 at 10:20
up vote 7 down vote accepted

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:

4815936072

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

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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