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



15
16
17
18
19
20
21
22
23
24
25
 
# File 'lib/DSA/algorithm.rb', line 15

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

.insertion_sort!(data) ⇒ Object

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



28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
# File 'lib/DSA/algorithm.rb', line 28

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



45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
# File 'lib/DSA/algorithm.rb', line 45

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