Nested For Loops for Numerical Inversions (Naive)

total_inversions.py

#! /bin/python3

def count_inversions(a):
    count = 0
    for i in range(0, len(a)):
        for j in range(i+1, len(a)):
            if a[i] > a[j]:
                count += 1
    return count

print(count_inversions([]), 0)
print(count_inversions([1, 2, 3]), 0)
print(count_inversions([2, 1, 3]), 1)
print(count_inversions([6, 5, 4, 3, 2, 1]), 15)
print(count_inversions([6, 5, 4, 3, 3, 3, 3, 2, 1]), 30)
print(count_inversions([1, 2, 3, 4]), 0)
print(count_inversions([1, 3, 2, 4]), 1)
print(count_inversions([4, 1, 2, 3]), 3)
print(count_inversions([4, 3, 2, 1]), 6)

totalInversions.js

#! /bin/nodejs

function countInversions(a) {
  var count = 0
  for (let i=0; i<a.length; ++i) {
    for (let j=i+1; j<a.length; ++j) {
      if (a[i] > a[j]) {
        count++
      }
    }
  }
  return count
}

console.log(countInversions([]), 0)
console.log(countInversions([1, 2, 3]), 0)
console.log(countInversions([2, 1, 3]), 1)
console.log(countInversions([6, 5, 4, 3, 2, 1]), 15)
console.log(countInversions([6, 5, 4, 3, 3, 3, 3, 2, 1]), 30)
console.log(countInversions([1, 2, 3, 4]), 0)
console.log(countInversions([1, 3, 2, 4]), 1)
console.log(countInversions([4, 1, 2, 3]), 3)
console.log(countInversions([4, 3, 2, 1]), 6)

Test script in local terminal emulator:

$ curl -s https://gist.githubusercontent.com/nick3499/a0683dccb076e631b8da30d87bec9907/raw/d8a979e061c86074de6e1bf53f8a34f1a65dc3a2/total_inversions.py | python3

• curl is like wget
• -s option silences extra stats
• | python3 pipes cURL's output to python3

Also test with local node installation.

[4, 3, 2, 1] has six numerical inversions because Y < X in the pairs [4, 3], [4, 2], [4, 1], [3, 2], [3, 1], and [2, 1], so [1, 2, 3, 4] has no such inversions, since Y > X persists through each iteration.