We can determine how "out of order" an array A is by counting the number of inversions it has. Two elements A[i] and A[j] form an inversion if A[i] > A[j] but i < j. That is, a smaller element appears after a larger element. Given an array, count the number of inversions it has. Do this faster than O(N^2) time. You may assume each element in the…

daily-coding-problem-44.rb

#!/usr/bin/env ruby

def out_of_order set 
    n = set.size()
    inv = 0
    n.times do |i| 
        (i+1...n).each do |j| 
            inv += 1 if set[i] > set[j]
        end
    end
    return inv
end 

set = [5, 4, 3, 2, 1]
puts out_of_order set