List of algorithms

The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.

If you intend to describe a new algorithm, please read algorithms on Wikipedia first, then add a link to your article and a one-line description here.

1 Combinatorial algorithms
- 1.1 General combinatorial algorithms
- 1.2 Graph algorithms
- 1.3 Search algorithms
- 1.4 String algorithms
  - 1.4.1 Searching
  - 1.4.2 Approximate matching
- 1.5 Sorting algorithms
- 1.6 Merge algorithms
2 Compression algorithms
- 2.1 Lossless compression algorithms
- 2.2 Lossy compression algorithms
3 Computational geometry
4 Computer graphics
5 Computer vision
6 Cryptographic algorithms
7 Digital signal processing
8 Software engineering
- 8.1 Distributed systems algorithms
- 8.2 Memory Allocation and deallocation algorithms
- 8.3 Operating systems algorithms
9 Electronics and hardware algorithms
10 Machine learning algorithms
11 Medical algorithms
12 Neural networks
13 Genetic algorithms
14 Numerical algebra
15 Number theoretic algorithms
16 Numerical algorithms
17 Optimization algorithms
18 Parsing
19 Quantum algorithms
20 Theory of computation and automata
21 Other

Combinatorial algorithms

General combinatorial algorithms

Floyd's cycle-finding algorithm: finds cycles in iterations
Pseudorandom number generators (uniformly distributed):
Robinson-Schensted algorithm: generates permutations from pairs of Young tableaux

Graph algorithms

Main article: graph theory

Bellman-Ford algorithm: computes shortest paths in a weighted graph (where some of the edge weights may be negative)
Dijkstra's algorithm: computes shortest paths in a graph with non-negative edge weights
Perturbation methods: an algorithm that computes a locally shortest paths in a graph
Floyd-Warshall algorithm: solves the all pairs shortest path problem in a weighted, directed graph
Johnson algorithm: All pairs shortest path algorithm in sparse weighted directed graph
Kruskal's algorithm: finds a minimum spanning tree for a graph
Prim's algorithm: finds a minimum spanning tree for a graph
Boruvka's algorithm: finds a minimum spanning tree for a graph
Ford-Fulkerson algorithm: computes the maximum flow in a graph
Edmonds-Karp algorithm: implementation of Ford-Fulkerson
Nonblocking Minimal Spanning Switch say, for a telephone exchange
Woodhouse-Sharp algorithm: finds a minimum spanning tree for a graph
Spring based algorithm: algorithm for graph drawing
Topological sort: finds linear order of nodes(e.g. jobs) based on their dependencies.
Hungarian algorithm: algorithm for finding a perfect matching
Coloring algorithm: Graph coloring algorithm.
Nearest neighbour algorithm
Blur Algorithm: Graphic Blur Algorithm.

Search algorithms

Linear search: finds an item in an unsorted list
Selection algorithm: finds the kth largest item in a list
Binary search algorithm: locates an item in a sorted list
Binary search tree: uses binary tree to maintain elements.
Breadth-first search: traverses a graph level by level
Depth-first search: traverses a graph branch by branch
Best-first search: traverses a graph in the order of likely importance using a priority queue
A* tree search: special case of best-first search that uses heuristics to improve speed
Uniform-cost search: a tree search that finds the lowest cost route where costs vary
Predictive search: binary like search which factors in magnitude of search term versus the high and low values in the search. Sometimes called dictionary search or interpolated search.
Hash table: finds an item in an unsorted collection in O(1) time.

String algorithms

Searching

Aho-Corasick algorithm: trie based algorithm for finding all matches in dictionary.
Bitap algorithm: fuzzy algorithm that determines strings are approximately equal.
Boyer-Moore string search algorithm: amortised linear (sublinear in most times) algorithm
Knuth-Morris-Pratt algorithm: bypasses reexamination of matched characters
Rabin-Karp string search algorithm: searches multiple patterns efficiently
Longest common subsequence problem: Haskell's dynamic programming algorithm
Longest increasing subsequence problem
Shortest common supersequence problem
longest common substring problem
Kadane's algorithm: finds maximum sub-array of any size
Boyer-Moore-Horspool algorithm

Approximate matching

Hirschberg's algorithm: space efficient algorithm for computing edit distance
Levenshtein edit distance
Metaphone: an algorithm for indexing words by their sound, when pronounced in English
Needleman-Wunsch algorithm
NYSIIS: phonetic algorithm
Smith-Waterman algorithm
Soundex

Sorting algorithms

Binary tree sort
Bogosort
Bubble sort: for each pair of indices, swap the items if out of order
Bucket sort
Cocktail sort
Comb sort
Counting sort
Gnome sort
Flashsort
Heapsort: convert the list into a heap, keep removing the largest element from the heap and adding it to the end of the list
Insertion sort: determine where the current item belongs in the list of sorted ones, and insert it there
Library sort
Merge sort: sort the first and second half of the list separately, then merge the sorted lists
Pancake sorting
Pigeonhole sort
Quicksort: divide list into two, with all items on the first list coming before all items on the second list.; then sort the two lists. Often the method of choice
Radix sort: sorts strings letter by letter
Selection sort: pick the smallest of the remaining elements, add it to the end of the sorted list
Shell sort: an attempt to improve insertion sort
Smoothsort
Topological sort

Merge algorithms

Simple Merge algorithm
k-way Merge algorithm

Compression algorithms

Lossless compression algorithms

Burrows-Wheeler transform: preprocessing useful for improving lossless compression
DEFLATE: lossless data compression
Delta encoding: aid to compression of data in which sequential data occurs frequently
Dynamic Markov Compression: Compression using predictive arithmetic coding
Incremental encoding: delta encoding applied to sequences of strings
LZW: lossless data compression (Lempel-Ziv-Welch)
LZ77 (algorithm): LZ77 and LZ78 are the names for the two lossless data compression algorithms
LZMA: short for Lempel-Ziv-Markov chain-Algorithm
LZO: data compression algorithm that is focused on speed
PPM compression algorithm
Shannon-Fano coding
Truncated binary encoding
Run-length encoding: lossless data compression taking advantage of strings of repeated characters
SEQUITUR algorithm: lossless compression by incremental grammar inference on a string
EZW (Embedded Zerotree Wavelet)
Entropy encoding: coding scheme that assigns codes to symbols so as to match code lengths with the probabilities of the symbols
- Huffman coding: simple lossless compression taking advantage of relative character frequencies
  - Adaptive Huffman coding: adaptive coding technique based on Huffman coding
  - Package-Merge: Optimizes Huffman coding subject to a length restriction on code strings
- Arithmetic coding: advanced entropy coding
  - Range encoding: same as arithmetic coding, but looked at in a slightly different way
Entropy coding with known entropy characteristics
- Unary coding: code that represents a number n with n ones followed by a zero
- Elias delta|gamma|omega coding: universal code encoding the positive integers
- Fibonacci coding: universal code which encodes positive integers into binary code words
- Golomb coding: form of entropy coding that is optimal for alphabets following geometric distributions
- Rice coding: form of entropy coding that is optimal for alphabets following geometric distributions

Lossy compression algorithms

Linear predictive coding: lossy compression by representing the spectral envelope of a digital signal of speech in compressed form
A-law algorithm: standard companding algorithm
Mu-law algorithm: standard analog signal compression or companding algorithm
Fractal compression: method used to compress images using fractals
Transform coding: type of data compression for "natural" data like audio signals or photographic images
Vector quantization: technique often used in lossy data compression
Wavelet compression: form of data compression well suited for image compression (sometimes also video compression and audio compression)

Computational geometry

Euclidean Distance Transform - Computes the distance between every point in a grid and a discrete collection of points.
Fortune's Algorithm: a well-known and simple-to-understand algorithm for computing Voronoi diagrams from a set of sites
Collision detection algorithms: check for the collision or intersection of two given solids
Convex hull algorithms: determining the convex hull of a set of points
- Chan's algorithm
- Gift wrapping algorithm or Jarvis march
- Graham scan
- Kirkpatrick–Seidel algorithm
Gilbert-Johnson-Keerthi distance algorithm: determining the smallest distance between two convex shapes.
Line segment intersection: finding whether lines intersect, usually with a sweep line algorithm
- Bentley-Ottmann algorithm
- Shamos-Hoey algorithm
Point in polygon algorithms: tests whether a given point lies within a given polygon
Polygon triangulation algorithms: decompose a polygon into a set of triangles

Computer graphics

Bresenham's line algorithm: plots points of a 2-dimensional array to form a straight line between 2 specified points (uses decision variables)
Line drawing algorithm: graphical algorithm for approximating a line segment on discrete graphical media.
DDA line algorithm: plots points of a 2-dimensional array to form a straight line between 2 specified points (uses floating-point math)
Flood fill: fills a connected region of a multi-dimensional array with a specified symbol
Xiaolin Wu's line algorithm: algorithm for line antialiasing.
Painter's algorithm: detects visible parts of a 3-dimensional scenery
Ray tracing: realistic image rendering
Phong shading: an illumination model and an interpolation method in 3D computer graphics
Gouraud shading: an algorithm to simulate the differing effects of light and colour across the surface of an object in 3D computer graphics
Scanline rendering: constructs an image by moving an imaginary line over the image
Global illumination algorithms: Considers direct illumination and reflection from other objects.
Interpolation: Constructing new data points such as in digital zoom.
Spline interpolation: Reduces error with Runge's phenomenon.

Computer vision

Epitome: represent an image or video by a smaller image or video.

Counting objects in an image: Counts the number of objects in a binary image. Uses the connected-component labeling algorithm to first label each object. Then returns the number of labeled objects.

Cryptographic algorithms

Main article: Cryptography

Digital signal processing

Main article: Digital signal processing

CORDIC: Fast trigonometric function computation technique.
Rainflow-counting algorithm: Reduces a complex stress history to a count of elementary stress-reversals for use in fatigue analysis
Osem: algorithm for processing of medical images
Goertzel algorithm Can be used for DTMF digit decoding.
Discrete Fourier transform: determines the frequencies contained in a (segment of a) signal
Iridix - image-processing algorithm for still image's and video enhancement
Richardson-Lucy deconvolution: image de-blurring algorithm
Elser Difference-Map Algorithm: X-Ray diffraction microscopy

Software engineering

Algorithms for Recovery and Isolation Exploiting Semantics: recovery
Unicode Collation Algorithm
CHS conversion: converting between disk addressing systems
Cyclic redundancy check: calculation of a check word
Parity: simple/fast error detection technique
Rayrole's algorithm: resource calendar management

Distributed systems algorithms

Lamport ordering: a partial ordering of events based on the happened-before relation
Snapshot algorithm: a snapshot is the process of recording the global state of a system
Vector clocks: a total ordering of events
Marzullo's algorithm: distributed clock synchronization
intersection algorithm: another clock agreement algorithm.
Byzantine fault tolerance: good fault tolerance.

Memory Allocation and deallocation algorithms

Boehm garbage collector: Conservative garbage collector
Buddy memory allocation: Algorithm to allocate memory such that fragmentation is less.
Generational garbage collector: Fast garbage collectors that segregate memory by age
Mark and sweep
Reference counting

Operating systems algorithms

Banker's algorithm: Algorithm used for deadlock avoidance.
Page replacement algorithms: Selecting the victim page under low memory conditions.
Bully algorithm: Selecting new leader among many computers.

Disk scheduling algorithms:

Elevator algorithm: Disk scheduling algorithm that works like an elevator.
Shortest seek first: Disk scheduling algorithm to reduce seek time.

Process synchronisation algorithms:

Scheduling algorithms

Electronics and hardware algorithms

Quine-McCluskey algorithm: Also called as Q-M algorithm, programmable method for simplyfying the boolean equations.
Petrick's method: Another algorithm for boolean simplification.
Espresso heuristic logic minimization: Fast algorithm for boolean function minimization.

Machine learning algorithms

Support Vector Machines

Medical algorithms

Neural networks

Main article: Neural networks

Genetic algorithms

Fitness proportionate selection - also known as roulette-wheel selection
Truncation selection
Tournament selection
Stochastic universal sampling

Numerical algebra

Buchberger's algorithm: finds a Gröbner basis
Eigenvalue algorithm
Exponentiating by squaring: quickly computes powers of numbers and matrices
Gram-Schmidt process: orthogonalizes a set of vectors
Knuth-Bendix completion algorithm: for rewriting rule systems
Multivariate division algorithm: for polynomials in several indeterminates

Number theoretic algorithms

Main article: Number theory

Discrete logarithm:
Euclidean algorithm: computes the greatest common divisor
Extended Euclidean algorithm: Also solves the equation ax+by = c.
Binary gcd algorithm: Efficient way of calculating gcd.
Integer factorization: breaking an integer into its prime factors
Multiplication algorithms: fast multiplication of two numbers
Booth's multiplication algorithm
Primality tests: determining whether a given number is prime
Odlyzko-Schönhage algorithm: calculates nontrivial zeroes of the Riemann zeta function

Numerical algorithms

Main article: numerical analysis

Biconjugate gradient method: solves systems of linear equations
Borwein's algorithm: an algorithm to calculate the value of 1/π
Dancing Links: finds all solutions to the exact cover problem
De Boor algorithm: computes splines
De Casteljau's algorithm: computes Bézier curves
False position method: approximates roots of a function
Gauss-Jordan elimination: solves systems of linear equations
Gauss–Seidel method: solves systems of linear equations iteratively
Gauss-Legendre algorithm: computes the digits of pi
Kahan summation algorithm: a more accurate method of summing floating-point numbers
Levinson recursion: solves equation involving a Toeplitz matrix
Metropolis-Hastings algorithm: used to generate a sequence of samples from the probability distribution of one or more variables
MISER algorithm: Monte Carlo simulation, numerical integration
Newton's method: finds zeros of functions with calculus
Risch algorithm: Translates indefinite integral to algebraic problem
Rounding functions: the classic ways to round numbers
Secant method: approximates roots of a function
Shifting nth-root algorithm: digit by digit root extraction
Square root: approximates the square root of a number
Strassen algorithm: faster matrix multiplication
Symbolic Cholesky decomposition: Efficient way of storing sparse matrix
Tridiagonal matrix algorithm (Thomas algorithm): solves systems of tridiagonal equations

Optimization algorithms

Ant colony optimization
BFGS method: A nonlinear optimization algorithm
Branch and bound
Chain matrix multiplication
Conjugate gradient
Differential evolution
Evolution strategy
Gauss-Newton algorithm: An algorithm for solving nonlinear least squares problems.
Genetic algorithms
Gradient descent
Interior point method
Karmarkar's algorithm: The first reasonably efficient algorithm that solves the linear programming problem in polynomial time.
Levenberg–Marquardt algorithm: An algorithm for solving nonlinear least squares problems.
Line search
Local search
Nelder-Mead method (downhill simplex method): A nonlinear optimization algorithm.
Newton's method in optimization
Particle swarm
Random-restart hill climbing
Simplex algorithm: An algorithm for solving the linear programming problem
Simulated annealing
Stochastic tunneling
Subset sum algorithm
Tabu search

Parsing

Recursive descent parser: A top-down parser suitable for LL(k) grammars
LL parser: A relatively simple linear time parsing algorithm for a limited class of context-free grammars
LR parser: A more complex linear time parsing algorithm for a larger class of context-free grammars. Variants:
Packrat parser: A linear time parsing algorithm supporting some context-free grammars and parsing expression grammars
CYK algorithm: An O(n3) algorithm for parsing any context-free grammar
Earley parser: Another O(n3) algorithm for parsing any context-free grammar
GLR parser:An algorithm for parsing any context-free grammar by Masaru Tomita. It is tuned for deterministic grammars, on which it performs almost linear time and O(n3) in worst case.
Inside-outside algorithm: An O(n3) algorithm for re-estimating production probabilities in probabilistic context-free grammars

Quantum algorithms

Application of quantum computation to various categories of problems and algorithms

Grover's algorithm: provides quadratic speedup for many search problems
Shor's algorithm: provides exponential speedup for factoring a number
Deutsch-Jozsa algorithm: criterion of balance for Boolean function

Theory of computation and automata

Powerset construction: Algorithm to convert nondeterministic automaton to deterministic automaton.
Todd-Coxeter algorithm: Procedure for generating cosets.

Other

Alpha max plus beta min algorithm: an approximation of the square-root of the sum of two squares.
Astronomical algorithms
Baum-Welch algorithm: hidden markov models
Bit manipulation algorithms: Create bit mask algorithm
Doomsday algorithm: day of the week
Schreier-Sims algorithm
Viterbi algorithm: hidden markov models
Xor swap algorithm: swaps the values of two variables without using a buffer
Luhn algorithm: a method of validating identification numbers
Rutishauser's algorithm
Stemming algorithm: a method of reducing words to their stem, base, or root form
Hamming weight (population count): find the number of 1 bits in a binary word
Heisenman-Drogulous isomoglobic algorithm
Gerchberg–Saxton algorithm: Phase retrieval algorithm for optical planes
Shunting yard algorithm: convert an infix-notation math expression to postfix