Module: DSA::Algorithm

Defined in:
lib/DSA/algorithm.rb

Class Method Summary collapse

Class Method Details

.binary_search(data, target, low, high) ⇒ Object

Binary search in sorted array



111
112
113
114
115
116
117
118
119
120
121
 
# File 'lib/DSA/algorithm.rb', line 111

def self.binary_search(data, target, low, high)
  return false if low > high
  middle = (low + high) / 2
  if data[middle] == target
    true
  elsif target < data[middle]
    binary_search data, target, low, middle-1
  else
    binary_search data, target, middle+1, high
  end
end

.factorial(n) ⇒ Object

Factorial function, the “Hello World” program of recursion



5
6
7
8
9
10
11
 
# File 'lib/DSA/algorithm.rb', line 5

def self.factorial(n)
  if n == 0
    1
  else
    n * factorial(n-1)
  end
end

.fibonacci(n) ⇒ Object 



14
15
16
 
# File 'lib/DSA/algorithm.rb', line 14

def self.fibonacci(n)
  self.fibonacci_logarithm(n)
end

.fibonacci_constant(n) ⇒ Object

It is kind of cheating, but mathematicians are unbelievable, they figured out a function to calculate the fibonacci sequence directly. There’s limitation on the 64-bit float numbers, so only use it to calculate small numbers.



104
105
106
107
 
# File 'lib/DSA/algorithm.rb', line 104

def self.fibonacci_constant(n)
  phi = 1.618034
  ((phi ** n - (1-phi) ** n) / Math.sqrt(5)).round
end

.fibonacci_exponential(n) ⇒ Object

we could implement fibonacci using recursion which looks simple, unfortunately, the running time of this algorithm itself is a fibonacci sequence, which grows fast, kind of exponential



20
21
22
23
24
25
26
27
28
29
30
31
32
 
# File 'lib/DSA/algorithm.rb', line 20

def self.fibonacci_exponential(n)
  if !n.is_a? Integer or n < 0
    raise ArgumentError
  end

  if n == 0
    0
  elsif n == 1
    1
  elsif n >= 2
    fibonacci_exponential(n-1) + fibonacci_exponential(n-2)
  end
end

.fibonacci_linear(n) ⇒ Object

fibonacci numbers



36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
 
# File 'lib/DSA/algorithm.rb', line 36

def self.fibonacci_linear(n)
  if !n.is_a? Integer or n < 0
    raise ArgumentError
  end

  if n == 0
    0
  elsif n == 1
    1
  elsif n >= 2
    a = 0
    b = 1
    2.upto(n) {
      b, a = a + b, b
    }
    b
  end
end

.fibonacci_logarithm(n) ⇒ Object

fibonacci sequences can be calculated in matrix multiplying

[f(n+1), f(n)], [f(n), f(n-1)]

equals [[1,1], [1,0]] to the nth

matrix multiplying can be achieved in logarithm time if we use divide and conquer



58
59
60
61
62
63
64
65
66
67
68
69
70
71
 
# File 'lib/DSA/algorithm.rb', line 58

def self.fibonacci_logarithm(n)
  if !n.is_a? Integer or n < 0
    raise ArgumentError
  end

  if n == 0
    0
  elsif n == 1
    1
  elsif n >= 2
    result = self.fibonacci_matrix_nth(n)
    result[0][1]
  end
end

.fibonacci_matrix_nth(n) ⇒ Object 



73
74
75
76
77
78
79
80
81
82
83
 
# File 'lib/DSA/algorithm.rb', line 73

def self.fibonacci_matrix_nth(n)
  first = [[1,1], [1,0]]
  if n == 1
    first
  elsif n % 2 == 0
    half = self.fibonacci_matrix_nth(n/2)
    square_matrix_multiply(half, half)
  else
    square_matrix_multiply(first, self.fibonacci_matrix_nth(n-1))
  end
end

.insertion_sort!(data) ⇒ Object

Insertion sort, n square worst running time, should not be used in general, built-in array sort is very good



124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
 
# File 'lib/DSA/algorithm.rb', line 124

def self.insertion_sort!(data)
  data.length.times do |index|
    this_value = data[index]
    j = index - 1
    while j >= -1
      if data[j] > this_value && j != -1
        data[j+1] = data[j]
      else
        data[j+1] = this_value
        break
      end
      j -= 1
    end
  end
end

.quick_sort!(data, low, high) ⇒ Object

in place quick sort



141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
 
# File 'lib/DSA/algorithm.rb', line 141

def self.quick_sort!(data, low, high)
  return if low >= high
  pivot = data[Random.rand(low..high)]
  left = low
  right = high
  while left <= right
    until left > right || data[left] >= pivot
      left += 1
    end
    until left > right || data[right] <= pivot
      right -= 1
    end
    if left <= right
      data[left], data[right] = data[right], data[left]
      left += 1
      right -= 1
    end
  end
  quick_sort!(data, low, right)
  quick_sort!(data, left, high)
end

.radix_sort(data) ⇒ Object

radix sort, in base 10



164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
 
# File 'lib/DSA/algorithm.rb', line 164

def self.radix_sort(data)
  goto_next_digit = true
  position = 0
  while goto_next_digit
    goto_next_digit = false
    buckets = []
    10.times { buckets << [] }
    data.each do |number|
      digit = get_digit(number, position)
      goto_next_digit = true if digit > 0 # if all digits are zero, loop will end
      buckets[digit] << number
    end
    data = buckets.flatten!
    position += 1
  end
  data
end

.sqrt(n) ⇒ Object 



182
183
184
185
186
187
188
189
 
# File 'lib/DSA/algorithm.rb', line 182

def self.sqrt(n)
  err = 1e-10
  r = Float(n)
  while (r - n/r).abs >= err
    r = ( r + n/r ) / 2
  end
  r
end

.square_matrix_multiply(a, b, size = 2) ⇒ Object 



85
86
87
88
89
90
91
92
93
94
95
96
97
98
 
# File 'lib/DSA/algorithm.rb', line 85

def self.square_matrix_multiply(a, b, size=2)
  result = []
  n = size - 1
  0.upto(n) do |i|
    result[i] = []
    0.upto(n) do |j|
      result[i][j] = 0
      0.upto(n) do |k|
        result[i][j] += a[i][k] * b[k][j]
      end
    end
  end
  result
end