A repository to hold sample code for a number of classic data structures implemented in ruby.
- Insertion Sort
- Sort an array using an insertion sort algorithm
- Merge Sort
- Sort an array using a merge sort algorithm
- Linked List
- Create and manipulate singly linked lists
- Stack
- Create a stack, push new nodes to it and pop the top node off
- ScoQueue
- Create a queue, enqueue and dequeue items and compute size
- Hash Table
- Create a hash table to store key/value pairs
- Binary Tree
- Traverse a binary tree using any of the three depth-first approaches: pre-order, in-order and post-order
- Benchmarks
- Use a rake task to see performance statistics for each data structure
- Travis CI
- Continuously tested!
The insertion sort algorithm is monkey-patched onto ruby's built-in Array
class, so to use it just call #insertion_sort
on an Array
object:
[3, 2, 5, 1, 4].insertion_sort
returns [1, 2, 3, 4, 5]
The insertion sort algorithm will immediately return the array if it only has one element in it. If there are multiple elements in the array, it creates an empty array, sorted
, and iterates forward through the original array pushing elements into sorted
. For each iteration of the original array, the element will be pushed onto the end of sorted
, and iterate backwards through sorted
until it hits a number smaller than it or the beginning of the array and then insert itself. For each backward iteration of sorted
, if the pushed element is smaller than the one its being compared to, the element from sorted will be assigned to the element one index up and the backwards iteration will continues. Once an element pushed into sorted
is compared to an element equal to or smaller than itself it is assigned to the current index and the backward iteration loop will break to jump to the next forward iteration of the original array.
Merge sort is also monkey-patched onto Array
. Like the insertion sort it will return an array sorted from lowest to highest, but works more consistently across arrays of generally increasing, decreasing or random ordering.
The merge_sort
algorithm calls itself recursively on an array until each element is in its own array, then it merges them back together in increasing order until they're all joined in a single array again. To accomplish this it depends on another method called merge
.
Array#merge
takes an array as an argument and depending on which is smaller will shift the first element off either self
or the input array into a new array, merged
, which it will return once all the elements from at least one of the arrays has been shifted out.
Array#merge_sort
works by spliting the Array
object (self
) in half and then calling merge_sort
on each half. The right half is then merge
-ed into the left half . Because merge_sort
calls itself recursively, each half of a given array will be split until it reaches that base case of a one element array.
Create a new instance of LinkedList
with an initial value of any type:
list = LinkedList.new(7)
To create a new Node
object you must at least pass it a value
; the second argument next_node
will default to nil
if nothing is given.
To insert a new node at the beginning of the list:
list.insert Node.new(6)
Now imagine our list has several more nodes:
Node.new(3, Node.new(4, Node.new(5, Node.new(6, Node.new(7, nil)))))
To search for a node with a given value:
list.search 5
This will return the Node
object with value 5
.
To remove a node with given value:
list.remove 6
This will return the Node
object with value 6
and remove it from the list.
To print all of the values of the list:
list.to_s
==> "3, 4, 5, 7"
To create a new stack pass it an initial value:
stack = Stack.new "Comment 1"
To add a new node to the top of the stack:
stack.push "Comment 2"
To pop the top node off the stack:
stack.pop
this will return a Node
object. You can access its value with the
#value
method.
So-named to avoid clashing with the Ruby built-in Queue
.
To make a new queue:
q = ScoQueue.new 'job 1'
To add a new node to the top of the queue:
q.enqueue 'job 2'
To compute the number of nodes in the queue:
q.size
returns: 2
To remove a node from the bottom of the queue:
q.dequeue
returns the value of the node: 'job 2'
To create a new hash table pass it a table size:
hash = HashTable.new 1024
Use the set(key, value)
method to enter a new key/value pair into the hash table (the key must be a String
):
hash.set 'team_1', 'Seattle Sounders FC'
To retrieve a value from the table, use the get(key)
method:
hash.get team_1
, which will return 'Seattle Sounders FC'
To delete a key/value pair from the hash table, use the delete(key)
method:
hash.delete team_1
, which will remove the pair and return the value .
The HashTable
object itself is actually very simple - its main job is to apply a hashing algorithm to a key and then delegate most of the hard work to another object called Bucket
. When a new key/value pair is set, the hashing algorithm will sum the ordinal numbers of each character in the key string together and then find the remainder of that sum divided by the number of slots in the hash's @table
instance variable, which is an Array
.
def hash(key)
key.chars.reduce(0) { |a, e| a + e.ord } % @size
end
That remainder will be the index of @table
in which the key/value will be insterted.
Each slot in @table
holds a linked list object called Bucket
. Each Bucket
has an instance variable @head
and methods to insert, search for, and remove key/value pairs. When a second item is set into the hash table with the same @table
index as an existing one, the new item replaces the node at that bucket's @head
and stores the previous node in its @nxt
instance variable. When a key/value pair is accessed either by get
or delete
, the hashing algorithm points to the right bucket, which then performs either search
or remove
and returns the result to the HashTable
object.
Create a new binary tree by passing it a value:
BinTree.new 'Root Value'
You can pass one or two new BinTree
objects as the second and third arguments when creating a new one:
tree = BinTree.new('root',
BinTree.new('left'),
BinTree.new('right')
)
*if you omit the second and/or third argument it will default to a NilBinTree
object
Each mode of traversal returns an Array
:
tree.pre_order # => ['root', 'left', 'right']
tree.in_order # => ['left', 'root', 'right']
tree.post_order # => ['left', 'right', 'root']
BinTree
provides the above three methods of traversal. They are very similar, so we'll focus just on pre-order traversal.
BinTree#pre_order
first creates an array called result
with only the tree's @value
attribute in it. It then recursively calls pre_order
on its @left
attribute and pushes each of the values from the resulting array into result
. Next it recursively calls pre_order
on its @right
attribute and again pushes the returned values into result
before returning result
.
This binary tree implementation makes use of the null-object pattern to deal with the recursive base-case. If an instance of BinTree
is initialized without an argument given for the left or right attributes, they will instead be assigned to a new instance of NilBinTree
.
NilBinTree
uses method_missing
to return an empty Array
when any of the traversal methods are called on it.
To run benchmarks, navigate to the root of the project directory in your terminal and enter:
$ rake bm
This will print performance statistics to the console:
- Fork It
- Create your feature branch (git checkout -b my-new-feature)
- Commit your changes (git commit -am 'Add some feature')
- Push to the branch (git push origin my-new-feature)
- Create new Pull Request
Linked list enlightenment found at visualgo
I learned about ruby exception handling at Ruby Learning
Ronald Kinch contributed to the implementation of Array#insertion_sort
Matt Yang contributed to the implementation of ScoQueue
This README was edited at dillinger.io
data_structures is released under the MIT License