## Linear search

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.

## Linked list

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

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

#### Binary Search

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.