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.
Combinatorial algorithms
General combinatorial algorithms
- Floyd's cycle-finding algorithm: finds cycles in iterations
- Pseudorandom number generators: producing statistically random output
- Blum Blum Shub: a pseudorandom number generator with a security proof
- Yarrow algorithm
Graph algorithms
See 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
- Floyd-Warshall algorithm: solves the all pairs shortest path problem in a 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
Combinatorial optimization
- Simplex algorithm
- Simulated annealing
- Subset-sum: Accepts the NP-complete language Subset-sum in polynomial time iff P=NP
Search algorithms
- Linear search: finds an item in an unsorted list
- Binary search: locates an item in a sorted list
- Binary search tree
- Breadth first search: traverses a tree level by level
- Depth first search: traverses a tree branch by branch
- Best-first search: traverses a tree in the order of likely importance using a priority queue
- A* tree search: special case of best-first search
- Predictive search: binary like search which factors in magnitude of search term versus the high and low values in the search. Sometimes called a dictionary search.
String searching algorithms
Sort algorithms
- Binary tree sort
- Bogosort: humorous and slow
- Bubble sort: for each pair of indices, swap the items if out of order
- 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
- Merge sort: sort the first and second half of the list separately, then merge the sorted lists
- 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
Compression algorithms
- Arithmetic coding: advanced entropy coding
- Burrows-Wheeler transform: preprocessing useful for lossless compression
- DEFLATE: lossless data compression
- Delta encoding: aid to compression of data in which sequential data occurs frequently
- Huffman coding: simple lossless compression
- Incremental encoding: delta encoding applied to sequences of strings
- Lessiss-Moore algorithm: deemed impractical
- LZW: lossless data compression (Lev, Zempel, Welch)
- Run-length encoding: lossless data compression
Computational geometry
- Gift wrapping algorithm: determining the convex hull of a set of points
- Graham scan determining the convex hull of a set of points in the plane
- Point in polygon: tests whether a given point lies within a given polygon
Computer graphics
- Bresenham's line algorithm: plots points of a 2-dimensional array to form a straight line between 2 specified points
- Flood fill: fills a connected region of a multi-dimensional array with a specified symbol
- Painter's algorithm: detects visible parts of a 3-dimensional scenery
- Ray tracing: realistic image rendering
Cryptographic algorithms
See also Topics in cryptography for an 'analytical glossary')
- Symmetric (secret key) encryption:
- Advanced Encryption Standard (AES), winner of NIST competition
- Blowfish
- Data Encryption Standard (DES), sometimes DE Algorithm, winner of NBS selection competition, replaced by AES for most purposes
- IDEA
- RC4 (cipher)
- Asymmetric (public key) encryption or digital signature:
- Cryptographic Message digest functions:
- MD5
- RIPEMD-160
- SHA-1
- HMAC: keyed-hash message authentication
- Other
- Diffie-Hellman: key exchange
- Diffie-Hellman: key exchange
Data visualization
- Spring based algorithms
Imaging
- Osem: Medical imaging
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 ordering: a total ordering of events
Numerical algorithms
See also main article numerical analysis and list of numerical analysis topics
- De Boor algorithm: computes splines.
- De Casteljau's algorithm: computes Bezier curves
- False position method: approximates roots of a function
- Gauss-Jordan elimination: solves systems of linear equations
- Gauss-Legendre algorithm: computes the digits of pi
- Newton's method: finds zeros of functions with calculus
- 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
Digital signal processing
- CORDIC: Fast trigonometric function computation technique.
- Fast Fourier transform: determines the frequencies contained in a (segment of a) signal
- Rainflow-counting algorithm: Reduces a complex stress history to a count of elementary stress-reversals for use in fatigue analysis
Number-theoretic algorithms
- Euclidean algorithm: computes the greatest common divisor
- Integer factorization: breaking an integer into its prime factors
- Multiplication algorithms: fast multiplication of two numbers
- Primality tests: determining whether a given number is prime
- AKS primality test
- Miller-Rabin primality test
- Sieve of Eratosthenes: produces a list of the first primes
Numerical algebra
- Buchberger's algorithm: finds a Grobner 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
Parsing
- CYK algorithm: decides whether a given string can be generated by a given context-free grammar
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. Is a number even or odd?
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 factorizing a number
- Deutsch-Jozsa algorithm: criterion of balance for Boolean function
Other
- Doomsday algorithm: Day of the week
- Halt: no one yet knows if this 43-byte C program ever halts
- Xor swap algorithm: swaps the values of two variables without using a buffer