title: What is the minimum number of swaps required to bubble sort an array?
body: <p>I'm trying to solve the Hackerrank problem <a href="https://www.hackerrank.com/challenges/new-year-chaos?h_r=next-challenge&amp;h_v=zen" rel="nofollow noreferrer">New Year Chaos</a>:</p>
  
  <p><a href="https://i.stack.imgur.com/DBaq0.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/DBaq0.png" alt="enter image description here"></a></p>
  
  <p>Further explanation can be found on the page. For example, denoting the 'swapped' queue as <code>q</code>, if <code>q = [2, 1, 5, 3, 4]</code>, then the required number of swaps is 3:</p>
  
  <p><a href="https://i.stack.imgur.com/oXzd0.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/oXzd0.png" alt="enter image description here"></a></p>
  
  <p>According to the first answer of <a href="https://www.quora.com/How-can-I-efficiently-compute-the-number-of-swaps-required-by-slow-sorting-methods-like-insertion-sort-and-bubble-sort-to-sort-a-given-array" rel="nofollow noreferrer">https://www.quora.com/How-can-I-efficiently-compute-the-number-of-swaps-required-by-slow-sorting-methods-like-insertion-sort-and-bubble-sort-to-sort-a-given-array</a>, the number of swaps required by bubble sort is equal to the number of inversions in the array. I tried to test this with the following Hackerrank submission:</p>
  
  <pre><code>#!/bin/python
  
  import sys
  
  
  T = int(raw_input().strip())
  for a0 in xrange(T):
      n = int(raw_input().strip())
      q = map(int,raw_input().strip().split(' '))
      # your code goes here
      diff = [x - y for x, y in zip(q, range(1,n+1))]
      if any([abs(el) &gt; 2 for el in diff]):
          print "Too chaotic"
      else:
          all_pairs = [(q[i], q[j]) for i in range(n) for j in range(i+1, n)]
          inversions = [pair[0] &gt; pair[1] for pair in all_pairs]
          print inversions.count(True)
  </code></pre>
  
  <p>Here is also a version of the code to run locally:</p>
  
  <pre><code>n = 5
  q = [2, 1, 5, 3, 4]
  
  diff = [x - y for x, y in zip(q, range(1,n+1))]
  if any([abs(el) &gt; 2 for el in diff]):
      print "Too chaotic"
  else:
      all_pairs = [(q[i], q[j]) for i in range(n) for j in range(i+1, n)]
      inversion_or_not = [pair[0] &gt; pair[1] for pair in all_pairs]
      print inversion_or_not.count(True)
  </code></pre>
  
  <p>For the given test case, the script correctly prints the number 3. However, for all the other 'hidden' test cases, it gives the wrong answer:</p>
  
  <p><a href="https://i.stack.imgur.com/J8PJA.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/J8PJA.png" alt="enter image description here"></a></p>
  
  <p>I've also tried a submission which implements bubble sort:</p>
  
  <pre><code>#!/bin/python
  
  import sys
  
  def swaps_bubble_sort(q):
      q = list(q)         # Make a shallow copy
      swaps = 0
      swapped = True
      while swapped:
          swapped = False
          for i in range(n-1):
              if q[i] &gt; q[i+1]:
                  q[i], q[i+1] = q[i+1], q[i]
                  swaps += 1
                  swapped = True
      return swaps
  
  T = int(raw_input().strip())
  for a0 in xrange(T):
      n = int(raw_input().strip())
      q = map(int,raw_input().strip().split(' '))
      # your code goes here
      diff = [x - y for x, y in zip(q, range(1,n+1))]
      if any([abs(el) &gt; 2 for el in diff]):
          print "Too chaotic"
      else:
          print swaps_bubble_sort(q)
  </code></pre>
  
  <p>but with the same (failed) result. Is the minimum number of swaps not equal to the number of inversions or that attained by bubble sort?</p>