forked from elvanja/codility
-
Notifications
You must be signed in to change notification settings - Fork 0
/
inversions.rb
44 lines (40 loc) · 1.11 KB
/
inversions.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# http://stackoverflow.com/questions/337664/counting-inversions-in-an-array
def merge(a, left, right)
i, j, count = 0, 0, 0
while (i < left.size || j < right.size) do
if i == left.size
a[i + j] = right[j]
j += 1
elsif j == right.size
a[i + j] = left[i]
i += 1
elsif left[i] <= right[j]
a[i + j] = left[i]
i += 1
else
a[i + j] = right[j]
count += left.size - i
j += 1
end
end
count
end
def solution(a)
return 0 if a.size < 2
middle = (a.size + 1) / 2
left = a[0..(middle - 1)]
right = a[middle..-1]
solution(left) + solution(right) + merge(a, left, right)
end
puts "result: #{solution([])}"
puts "result: #{solution([1])}"
puts "result: #{solution([1, 5])}"
puts "result: #{solution([4, 1])}"
puts "result: #{solution([4, 1, 2, 3, 9])}"
puts "result: #{solution([4, 1, 3, 2, 9, 5])}"
puts "result: #{solution([4, 1, 3, 2, 9, 1])}"
puts "result: #{solution([6, 9, 1, 14, 8, 12, 3, 2])}"
puts "result: #{solution([1, 2, 3, 4, 5, 6])}"
sample = []
(1..100_000).each { |i| sample << (rand * 100_000).to_int }
puts "result: #{solution(sample)}"