Class: DivideAndConquerStrategy

Inherits:
Object
  • Object
show all
Defined in:
lib/inversions_in_array/divide_and_conquer_strategy.rb

Instance Method Summary collapse

Instance Method Details

#inversions(array) ⇒ Object 



31
32
33
 
# File 'lib/inversions_in_array/divide_and_conquer_strategy.rb', line 31

def inversions(array)    
  sort_and_calculate_inversions(array)[0]
end

#merge(left_i, right_i) ⇒ Object 



2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
# File 'lib/inversions_in_array/divide_and_conquer_strategy.rb', line 2

def merge(left_i,right_i)
  left = left_i[1]
  right = right_i[1]
  sorted = []
  inversions = left_i[0] + right_i[0]
  until left.empty? or right.empty?
    if left.first <= right.first        
      sorted << left.shift
    else
      sorted << right.shift

      if !left.empty?
        inversions = inversions + left.size
      end
    end      
  end
  return inversions, sorted.concat(left).concat(right)
end

#sort_and_calculate_inversions(array) ⇒ Object 



21
22
23
24
25
26
27
28
29
 
# File 'lib/inversions_in_array/divide_and_conquer_strategy.rb', line 21

def sort_and_calculate_inversions(array)
  return 0, array if array.size <= 1

  mid = (array.size / 2).to_i
  left = array[0,mid]
  right = array[mid,array.size - mid]

  merge(sort_and_calculate_inversions(left),sort_and_calculate_inversions(right))
end