algorithms.rb

The ‘Algorithms and Containers’ library is an effort to provide a set of commonly used algorithms and containers to Ruby programmers.

This is a Google Summer of Code 2008 project

Written by Kanwei Li, mentored by Austin Ziegler

To avoid typing Containers::xxx to initialize containers, include the Containers module.

require 'algorithms'
include Containers

tree = RBTreeMap.new

instead of:

require 'algorithms'

tree = Containers::RBTreeMap.new

Done so far:

• Heaps - Containers::Heap, Containers::MaxHeap, Containers::MinHeap

• Priority Queue - Containers::PriorityQueue

• Stack - Containers::Stack

• Queue - Containers::Queue

• Deque - Containers::Deque, Containers::CDeque (C extension), Containers::RubyDeque

• Red-Black Trees - Containers::RBTreeMap, Containers::CRBTreeMap (C extension), Containers::RubyRBTreeMap

• Splay Trees - Containers::SplayTreeMap

• Tries - Containers::Trie

• Suffix Array - Containers::SuffixArray

• kd Tree - Containers::KDTree

• Search algorithms

  • Binary Search - Algorithms::Search.binary_search

  • Knuth-Morris-Pratt - Algorithms::Search.kmp_search

• Sort algorithms

  • Bubble sort - Algorithms::Sort.bubble_sort

  • Comb sort - Algorithms::Sort.comb_sort

  • Selection sort - Algorithms::Sort.selection_sort

  • Heapsort - Algorithms::Sort.heapsort

  • Insertion sort - Algorithms::Sort.insertion_sort

  • Shell sort - Algorithms::Sort.shell_sort

  • Quicksort - Algorithms::Sort.quicksort

  • Mergesort - Algorithms::Sort.mergesort

  • Dual-Pivot Quicksort - Algorithms::Sort.dualpivotquicksort

• String algorithms

  • Levenshtein distance - Algorithms::String.levenshtein_dist