[English]July 29, 2015

This is a list of six algorithms written in Ruby. I did this as an exercise a long time ago when I was learning the language.

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
@head = @tail = nil
end
def add(value)
node = Node.new(value)
@head = node if @head.nil?
@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
list = LinkedList.new()
list.add(1)
# => current: 1, head: true, tail: true, next: nil
list.add(2)
# => current: 2, head: false, tail: true, next: nil
list.add(3)
# => 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
node = @head
i = 0
loop do
prev = node
node = node.next
i += 1
break unless !node.nil? and i < index
end
if prev.nil?
@head = node.next
else
prev.next = node.next
end
end
```

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
def add(value)
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]
hash.add('foo')
# => [nil, nil, "foo"]
hash.add('bar')
# => ["bar", nil, "foo"]
hash.add('candy')
# => ["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|
@buckets[i] = LinkedList.new
end
end
def add(value)
#...
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
```

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
```

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
```

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.