List of algorithms

The following is a list of the algorithms described in Wikipedia. See also the list of 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.

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 oftenly
Huffman coding: simple lossless entropy coding
LZW: lossless data compression
Run-length encoding: lossless data compression

Cryptographic algorithms:

Symmetric (secret key) encryption:
- AES
- Blowfish
- DES
- IDEA
- RC4
Asymmetric (public key) encryption or digital signature:
Message digest:
Other:
- Diffie-Hellman: key exchange
- HMAC: keyed-hash message authentication

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:

Euclidean algorithm: computes the greatest common divisor
Exponentiating by squaring: quickly computes powers of numbers and matrices
Fast Fourier transform: determines the frequencies contained in a (segment of a) signal
Gauss-Jordan elimination: solves systems of linear equations
Gauss-Legendre algorithm: computes the digits of pi
Gram-Schmidt process: orthogonalizes a set of vectors
Integer factorization: breaking an integer into its prime factors
- Lenstra elliptic curve factorization
- General number field sieve
Multiplication algorithms: fast multiplication of two numbers
Primality tests: determining whether a given number is prime
- Miller-Rabin primality test
- Sieve of Eratosthenes: produces a list of the first primes
Newton's method: finds zeros of functions with calculus
Pseudorandom number generators: producing statistically random output
- Blum Blum Shub: a pseudorandom number generator with a security proof
- Yarrow algorithm
Rounding functions: the classic ways to round numbers
Square root: approximates the square root of a number

Parsing:

CYK algorithm: decides whether a given string can be generated by a given context-free grammar

Quantum algorithms:

Grover's algorithm: provides quadratic speedup for many search problems
Shor's algorithm: provides exponential speedup for factorizing a number

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 insertions sort

Graph algorithms:

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
Nonblocking Minimal Spanning Switch say, for a Telephone exchange

Data visualization:

spring based algorithms

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 test: 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

Other:
- Xor swap algorithm: swaps the values of two variables without using a buffer