# Six classic algorithms in Ruby

29 de julio del 2015 — 1617 palabras — 8 min

This is a basic search algorithm. It iterates in a collection or in a data structure until it finds a value that matches.

``````def findIndex(values, target)
values.each_with_index do |value, i|
return i if value == target
end
end

findIndex([4, 8, 15, 16, 23, 42], 15)
# => 2
``````

The function iterates over each value of an array and compares the index with the value in memory. If this matches, the index is returned.

Linear data structure where each object, called nodes, is linked to its predecessor and sometimes to its successor.

``````class LinkedList
def initialize
end

node = Node.new(value)

@tail.next = node unless @tail.nil?

@tail = node
end
end

class Node
def initialize(value)
@value = value
@next = nil
end

def next
@next
end

def next=(value)
@next = value
end
end

# => current: 1, head: true, tail: true, next: nil
# => current: 2, head: false, tail: true, next: nil
# => current: 3, head: false, tail: true, next: nil

# Final Result
# Current: 1, head: true, tail: false, next: 2
# Current: 2, head: false, tail: false, next: 3
# Current: 3, head: false, tail: true, next: nil
``````

To manipulate the `LinkedList` class we will have to update the reference of the `head`, `tail` and `next` attributes. The following example corresponds to the update of values if one was removed.

``````def removeAt(index)
prev = nil
i = 0
loop do
prev = node
node = node.next
i += 1
break unless !node.nil? and i < index
end
if prev.nil?
else
prev.next = node.next
end
end
``````

## Hash table

The basic concept of a hash table is to insert a value in a bucket based on its hashed value.

``````class HashTable
def initialize(size)
@size = size
@buckets = Array.new(@size)
end

index = hash(value)
@buckets[index] = value
end

def hash(value)
sum = 0
0.upto(value.size-1) do |i|
sum += value[i].ord - 97
end
return sum % @size
end
end

hash = HashTable.new(3)
# => [nil, nil, nil]

# => [nil, nil, "foo"]

# => ["bar", nil, "foo"]

# => ["bar", "candy", "foo"]
``````

The hashing is prior to cause collisions, it’s part of the nature of this type of algoritm (see Birthday Problem). A way to deal with this is by using a Linked List, for example:

``````class LinkedList
#...
end

class Node
#...
end

class HashTable
def initialize(size)
@size = size
@buckets = Array.new(@size)
0.upto(@size) do |i|
end
end

#...
end

def hash(value)
#...
end
end
``````

It is based on the principle of divide and conquer in order to find a value in an ordered list.

``````def findIndex(values, target)
binarySearch(values, target, 0, values.size - 1)
end

def binarySearch(values, target, start, finish)
return -1 if start > finish

middle = ((start+finish)/2).floor
value = values[middle]

puts "From #{start} to #{finish}. Middle: #{middle}"

return binarySearch(values, target, start, middle-1) if value > target
return binarySearch(values, target, middle+1, finish) if value < target

puts "Result: #{middle}"
return middle
end

findIndex([2, 4, 6, 8, 10, 12, 14, 16, 18, 20], 6)

# =>
# From 0 to 9. Middle: 4
# From 0 to 3. Middle: 1
# From 2 to 3. Middle: 2
# Result: 2
``````

#### Bubble Sort

It is the most basic way to order a collection. It iterates over each value and compares with the next and switch places if necessary. The iteration is repeated until all the values are not interchangeable.

``````def sort(values)
length = values.size - 2
swapped = true

while swapped
swapped = false

0.upto(length) do |i|
if values[i] > values[i+1]
values[i], values[i+1] = values[i+1], values[i]
swapped = true
end
end
end

return values
end

sort([7, 4, 5, 2, 9, 1])

# output in each step
# =>
# 7, 4, 5, 2, 9, 1
# 4, 5, 2, 7, 1, 9
# 4, 2, 5, 1, 7, 9
# 2, 4, 1, 5, 7, 9
# 2, 1, 4, 5, 7, 9
# 1, 2, 4, 5, 7, 9
``````

#### Insertion Sort

Unlike Bubble Sort, this algorithm inserts the iterated value in the correct place based on their ancestors making a comparison with each one.

``````def sort(values)
length = values.size - 1

1.upto(length) do |i|
temp = values[i]
j = i - 1

while j >= 0 and values[j] > temp
values[j+1] = values[j]
j -= 1
end

values[j+1] = temp
end

return values
end

puts sort([7, 4, 5, 2, 9, 1])

# output in each step
# =>
# 4, 7, 5, 2, 9, 1
# 4, 5, 7, 2, 9, 1
# 2, 4, 5, 7, 9, 1
# 2, 4, 5, 7, 9, 1
# 1, 2, 4, 5, 7, 9
``````

## Final notes

I’m not very good at algorithms and probably these versions can be better, but it was very fun exercise. I found really good sources and explanations while I was researching each of these algorithms.

I really recommend checking out The Sound of Sorting, it’s a small program that helps out to visualize and hear various sorting algorithms.

Lo último de Ruby on Rails en Español

Suscríbete al newsletter bimensual de EnRails y recibe lo último de Ruby on Rails en Español en tu bandeja de entrada. Incluye noticias, cambios importantes, artículos, gemas interesantes, bolsa de trabajo y mucho mas.

Al registrarte declaras aceptar los términos y condiciones de uso y la política de privacidad de Revue.