What is the minimum number of swaps required to bubble sort an array?
<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">New Year Chaos</a>:</p>

<p><a href="http://i.stack.imgur.com/DBaq0.png" rel="nofollow"><img src="http://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="http://i.stack.imgur.com/oXzd0.png" rel="nofollow"><img src="http://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">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="http://i.stack.imgur.com/J8PJA.png" rel="nofollow"><img src="http://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>

<p>You just have to count the number of necessary swaps in bubble sort. Here is my code that got accepted.</p>

<pre><code>T = input()
for test in range(T):
    n = input()
    l = map(int, raw_input().split())
    for i,x in enumerate(l):
        if x-(i+1) &gt; 2:
            print "Too chaotic"
            break
    else:
        counter = 0
        while 1:
            flag = True
            for i in range(len(l)-1):
                if l[i] &gt; l[i+1]:
                    l[i],l[i+1] = l[i+1],l[i]
                    counter += 1
                    flag = False
            if flag:
                break
        print counter
</code></pre>

<p>In your first code your approach is <code>O(n^2)</code> which is not appropriate for <code>n = 10^5</code>. In this line </p>

<pre><code>all_pairs = [(q[i], q[j]) for i in range(n) for j in range(i+1, n)]
</code></pre>

<p>you are trying to store <code>10^10</code> tuples in your RAM.</p>

<p>The problem with your second code is you are using the <code>abs</code> of elements of diff to make sure the array is not chaotic. However one person can go to the end of the line only by getting bribed and it doesn't violates the rules. So you just have to make sure a person doesn't come forward more than two positions not the other way around.</p>

python algorithm sorting