Module: Algorithms

Defined in:

lib/algorithms.rb,
ext/algorithms/string/string.c

Overview

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

Defined Under Namespace

Modules: Search, Sort, String