djo/algorithms

Basic Algorithms written in Ruby

Basic Algorithms written in Ruby

Fundamentals

• The greatest common divisor
• Transpose of a matrix in Linear Algebra
• Find the k-th smallest value in the array
• Work with a linked list
• Dijkstra's two-stack algorithm for expression evaluation
• Union-find algorithm (weighted quick-union implementation)

Sorting

• Selection sort
• Insertion sort
• Shell sort
• Top-down mergesort
• Bottom-up mergesort of a linked list
• Quick sort
• Quick 3-way sort
• Heap sort
• Max-oriented priority queue

Searching

• Check if a binary tree is balanced
• Find the 'next' node (in-order successor) of a given node in a binary search tree

Graphs

• Depth-first search
• Finding a directed cycle

Strings

• Least-significant-digit first string sort

Development:

bundle install
bundle exec rake test

Copyright (C) 2013-2014 Andrew Djoga, released under the MIT license.