module DSA::Algorithm

Public Class Methods

factorial(n) click to toggle source

Factorial function, the “Hello World” program of recursion

# File lib/DSA/algorithm.rb, line 5
def self.factorial(n)
  if n == 0
    1
  else
    n * factorial(n-1)
  end
end
fibonacci(n) click to toggle source
# File lib/DSA/algorithm.rb, line 14
def self.fibonacci(n)
  self.fibonacci_logarithm(n)
end
fibonacci_constant(n) click to toggle source

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.

# 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) click to toggle source

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

# 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) click to toggle source

fibonacci numbers

# 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) click to toggle source

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

# 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) click to toggle source
# 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) click to toggle source

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

# 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) click to toggle source

in place quick sort

# 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) click to toggle source

radix sort, in base 10

# 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) click to toggle source
# 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) click to toggle source
# 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

Private Class Methods

get_digit(number, position) click to toggle source
# File lib/DSA/algorithm.rb, line 193
def self.get_digit(number, position)
  number % (10 ** (position+1)) / (10 ** position)
end