Editing List of algorithms (section)

==Combinatorial algorithms==
{{further| Combinatorics}}

===General combinatorial algorithms===
* [[Cycle detection#Brent's algorithm|Brent's algorithm]]: finds a cycle in function value iterations using only two iterators<ref>{{Cite journal |last=Gegenfurtner |first=Karl R. |date=1992-12-01 |title=PRAXIS: Brent's algorithm for function minimization |journal=Behavior Research Methods, Instruments, & Computers |language=en |volume=24 |issue=4 |pages=560–564 |doi=10.3758/BF03203605 |issn=1532-5970|doi-access=free }}</ref>
* [[Floyd's cycle-finding algorithm]]: finds a cycle in function value iterations<ref>{{Cite web |date=2013-09-30 |title=richardshin.com {{!}} Floyd's Cycle Detection Algorithm |url=http://www.richardshin.com/floyds-cycle-detection-algorithm/ |access-date=2023-10-26 |language=en-US}}</ref>
* [[Gale–Shapley algorithm]]: solves the [[stable matching problem]]<ref>{{cite web |author=Tesler, G.|url=https://mathweb.ucsd.edu/~gptesler/154/slides/154_galeshapley_20-handout.pdf|website=mathweb.ucsd.edu|title=Ch. 5.9: Gale-Shapley Algorithm|date= 2020|publisher=[[University of California San Diego]]|access-date=26 April 2025|url-status=|archive-url=|archive-date=}}</ref><ref>{{cite web|last1=Kleinberg|first1=Jon |last2=Tardos|first2=Éva |url=https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/01StableMatching.pdf|website=www.cs.princeton.edu|title=Algorithmn Design: 1. Stable Matching|date= 2005|publisher=[[Pearson PLC|Pearson]]-[[Addison Wesley]]: [[Princeton University]]|access-date=26 April 2025|url-status=|archive-url=|archive-date=}}</ref><ref>{{cite web |last1=Goel|first1=Ashish |editor1-last=Ramseyer|editor1-first=Geo  |url=https://web.stanford.edu/~ashishg/cs261/win21/notes/l5_note.pdf|website=web.stanford.edu|title=CS261 Winter 2018- 2019 Lecture 5: Gale-Shapley Algorith|date= 21 January 2019|publisher=[[Stanford University]]|access-date=26 April 2025|url-status=|archive-url=|archive-date=}}</ref>
* [[Pseudorandom number generator]]s (uniformly distributed—see also [[List of random number generators#Pseudorandom number generators (PRNGs)|List of pseudorandom number generators]] for other PRNGs with varying degrees of convergence and varying statistical quality):{{citation needed|date=June 2024}}
** [[ACORN (PRNG)|ACORN generator]]
** [[Blum Blum Shub]]
** [[Lagged Fibonacci generator]]
** [[Linear congruential generator]]
** [[Mersenne Twister]]

===Graph algorithms===
{{further|Graph theory|:Category:Graph algorithms}}
* [[Coloring algorithm]]: Graph coloring algorithm.
* [[Hopcroft–Karp algorithm]]: convert a bipartite graph to a [[maximum cardinality matching]]
* [[Hungarian algorithm]]: algorithm for finding a [[perfect matching]]
* [[Prüfer sequence|Prüfer coding]]: conversion between a labeled tree and its [[Prüfer sequence]]
* [[Tarjan's off-line lowest common ancestors algorithm]]: computes [[lowest common ancestor]]s for pairs of nodes in a tree
* [[Topological sorting|Topological sort]]: finds linear order of nodes (e.g. jobs) based on their dependencies.

====Graph drawing====
{{further|Graph drawing}}
* [[Force-based algorithms (graph drawing)|Force-based algorithms]] (also known as force-directed algorithms or spring-based algorithm)
* [[Spectral layout]]

====Network theory====
{{further|Network theory}}
* Network analysis
** Link analysis
*** [[Girvan–Newman algorithm]]: detect communities in complex systems
*** Web link analysis
**** [[Hyperlink-Induced Topic Search]] (HITS) (also known as [[Hubs and authorities]])
**** [[PageRank]]
**** [[TrustRank]]
* [[Flow network]]s
** [[Dinic's algorithm]]: is a [[strongly polynomial]] algorithm for computing the [[maximum flow]] in a [[flow network]].
** [[Edmonds–Karp algorithm]]: implementation of Ford–Fulkerson
** [[Ford–Fulkerson algorithm]]: computes the [[maximum flow problem|maximum flow]] in a graph
** [[Karger's algorithm]]: a Monte Carlo method to compute the [[minimum cut]] of a connected graph
** [[Push–relabel algorithm]]: computes a [[maximum flow problem|maximum flow]] in a graph

====Routing for graphs====
* [[Edmonds' algorithm]] (also known as Chu–Liu/Edmonds' algorithm): find maximum or minimum branchings
* [[Euclidean minimum spanning tree]]: algorithms for computing the minimum spanning tree of a set of points in the plane
* [[Longest path problem]]: find a simple path of maximum length in a given graph
* [[Minimum spanning tree]]
** [[Borůvka's algorithm]]
** [[Kruskal's algorithm]]
** [[Prim's algorithm]]
** [[Reverse-delete algorithm]]
* [[Nonblocking minimal spanning switch]] say, for a [[telephone exchange]]
* [[Vehicle routing problem]]
** Clarke and Wright Saving algorithm
* [[Shortest path problem]]
** [[Bellman–Ford algorithm]]: computes [[shortest path problem|shortest paths]] in a weighted graph (where some of the edge weights may be negative)
** [[Dijkstra's algorithm]]: computes [[shortest path problem|shortest paths]] in a graph with non-negative edge weights
** [[Floyd–Warshall algorithm]]: solves the [[shortest path problem#All-pairs shortest paths|all pairs shortest path]] problem in a weighted, directed graph
** [[Johnson's algorithm]]: all pairs shortest path algorithm in sparse weighted directed graph
<!-- ** [[Perturbation methods]]: an algorithm that computes a locally [[shortest path problem|shortest paths]] in a graph -->
* [[Transitive closure]] problem: find the [[transitive closure]] of a given binary relation
* [[Traveling salesman problem]]
** [[Christofides algorithm]]
** [[Nearest neighbour algorithm]]
* [[Warnsdorff's rule]]: a heuristic method for solving the [[Knight's tour]] problem

====Graph search====
{{further|State space search|Graph search algorithm}}
* [[A* search algorithm|A*]]: special case of best-first search that uses heuristics to improve speed
* [[B*]]: a best-first graph search algorithm that finds the least-cost path from a given initial node to any goal node (out of one or more possible goals)
* [[Backtracking]]: abandons partial solutions when they are found not to satisfy a complete solution
* [[Beam search]]: is a heuristic search algorithm that is an optimization of [[best-first search]] that reduces its memory requirement
* [[Beam stack search]]: integrates backtracking with [[beam search]]
* [[Best-first search]]: traverses a graph in the order of likely importance using a [[priority queue]]
* [[Bidirectional search]]: find the shortest path from an initial vertex to a goal vertex in a directed graph
* [[Breadth-first search]]: traverses a graph level by level
* [[Brute-force search]]: an exhaustive and reliable search method, but computationally inefficient in many applications
* [[D*]]: an [[incremental heuristic search]] algorithm
* [[Depth-first search]]: traverses a graph branch by branch
* [[Dijkstra's algorithm]]: a special case of A* for which no heuristic function is used
* [[General Problem Solver]]: a seminal theorem-proving algorithm intended to work as a universal problem solver machine.
* [[Iterative deepening depth-first search]] (IDDFS): a state space search strategy
* [[Jump point search]]: an optimization to A* which may reduce computation time by an order of magnitude using further heuristics
* [[Lexicographic breadth-first search]] (also known as Lex-BFS): a linear time algorithm for ordering the vertices of a graph
* [[Uniform-cost search]]: a [[Tree traversal|tree search]] that finds the lowest-cost route where costs vary
* [[SSS*]]: state space search traversing a game tree in a best-first fashion similar to that of the A* search algorithm

====Subgraphs====
* [[Clique (graph theory)|Cliques]]
** [[Bron–Kerbosch algorithm]]: a technique for finding [[maximal clique]]s in an undirected graph
** [[MaxCliqueDyn maximum clique algorithm]]: find a [[maximum clique]] in an undirected graph
* [[Strongly connected components]]
** [[Path-based strong component algorithm]]
** [[Kosaraju's algorithm]]
** [[Tarjan's strongly connected components algorithm]]
* [[Subgraph isomorphism problem]]

===Sequence algorithms===
{{further|Sequences}}

====Approximate sequence matching====
* [[Bitap algorithm]]: fuzzy algorithm that determines if strings are approximately equal.
* [[Phonetic algorithm]]s
** [[Daitch–Mokotoff Soundex]]: a [[Soundex]] refinement which allows matching of Slavic and Germanic surnames
** [[Double Metaphone]]: an improvement on Metaphone
** [[Match rating approach]]: a phonetic algorithm developed by Western Airlines
** [[Metaphone]]: an algorithm for indexing words by their sound, when pronounced in English
** [[New York State Identification and Intelligence System|NYSIIS]]: [[phonetic algorithm]], improves on [[Soundex]]
** [[Soundex]]: a phonetic algorithm for indexing names by sound, as pronounced in English
* [[String metric]]s: computes a similarity or dissimilarity (distance) score between two pairs of text strings
** [[Damerau–Levenshtein distance]]: computes a distance measure between two strings, improves on [[Levenshtein distance]]
** [[Dice's coefficient]] (also known as the Dice coefficient): a similarity measure related to the [[Jaccard index]]
** [[Hamming distance]]: sum number of positions which are different
** [[Jaro–Winkler distance]]: is a measure of similarity between two strings
** [[Levenshtein distance|Levenshtein edit distance]]: computes a metric for the amount of difference between two sequences
* [[Trigram search]]: search for text when the exact syntax or spelling of the target object is not precisely known

====Selection algorithms====
{{main|Selection algorithm}}
* [[Quickselect]]
* [[Introselect]]

====Sequence search====
* [[Linear search]]: locates an item in an unsorted sequence
* [[Selection algorithm]]: finds the ''k''th largest item in a sequence
* [[Ternary search]]: a technique for finding the minimum or maximum of a function that is either strictly increasing and then strictly decreasing or vice versa
* [[Sorted list]]s
** [[Binary search algorithm]]: locates an item in a sorted sequence
** [[Fibonacci search technique]]: search a sorted sequence using a divide and conquer algorithm that narrows down possible locations with the aid of [[Fibonacci numbers]]
** [[Jump search]] (or block search): linear search on a smaller subset of the sequence
** [[Interpolation search|Predictive search]]: binary-like search which factors in [[magnitude (mathematics)|magnitude]] of search term versus the high and low values in the search.  Sometimes called dictionary search or interpolated search.
** [[Uniform binary search]]: an optimization of the classic binary search algorithm
** [[Eytzinger binary search]]: cache friendly binary search algorithm <ref>{{Cite web |title=Eytzinger Binary Search - Algorithmica |url=https://algorithmica.org/en/eytzinger |access-date=2023-04-09}}</ref>

====Sequence merging====
{{main|Merge algorithm}}
* Simple merge algorithm
* [[k-way merge algorithm]]
* Union (merge, with elements on the output not repeated)

====Sequence permutations====
{{further|Permutation}}
* [[Fisher–Yates shuffle]] (also known as the Knuth shuffle): randomly shuffle a finite set
* [[Schensted algorithm]]: constructs a pair of [[Young tableau]]x from a permutation
* [[Steinhaus–Johnson–Trotter algorithm]] (also known as the Johnson–Trotter algorithm): generates permutations by transposing elements
* [[Heap's algorithm|Heap's permutation generation algorithm]]: interchange elements to generate next permutation

====Sequence combinations====
{{further|Combination}}

====Sequence alignment====
* [[Dynamic time warping]]: measure similarity between two sequences which may vary in time or speed
* [[Hirschberg's algorithm]]: finds the least cost [[sequence alignment]] between two sequences, as measured by their [[Levenshtein distance]]
* [[Needleman–Wunsch algorithm]]: find global alignment between two sequences
* [[Smith–Waterman algorithm]]: find local sequence alignment

====Sequence sorting====
{{main|Sorting algorithm}}
{{contradicts other|Sorting_algorithm#Comparison_of_algorithms|date=March 2011}}

* Exchange sorts
** [[Bubble sort]]: for each pair of indices, swap the items if out of order
** [[Cocktail shaker sort]] or bidirectional bubble sort, a bubble sort traversing the list alternately from front to back and back to front
** [[Comb sort]]
** [[Gnome sort]]
** [[Odd–even 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
* Humorous or ineffective
** [[Bogosort]]: the list is randomly shuffled until it happens to be sorted
** [[Slowsort]]
** [[Stooge sort]]
** [[Stalin sort]]: all elements that are not in order are removed from the list<ref>{{cite web | title=A "Sorting" algorithm | website=Code Golf Stack Exchange | date=October 30, 2018 | url=https://codegolf.stackexchange.com/questions/174964/a-sorting-algorithm | access-date=April 4, 2025}}</ref>
* Hybrid
** [[Flashsort]]
** [[Introsort]]: begin with quicksort and switch to heapsort when the recursion depth exceeds a certain level
** [[Timsort]]: adaptative algorithm derived from merge sort and insertion sort. Used in Python 2.3 and up, and Java SE 7.
* Insertion sorts
** [[Insertion sort]]: determine where the current item belongs in the list of sorted ones, and insert it there
** [[Library sort]]
** [[Patience sorting]]
** [[Shellsort|Shell sort]]: an attempt to improve insertion sort
** [[Tree sort]] (binary tree sort): build binary tree, then traverse it to create sorted list
** [[Cycle sort]]: in-place with theoretically optimal number of writes
* Merge sorts
** [[Merge sort]]: sort the first and second half of the list separately, then merge the sorted lists
** [[Slowsort]]
** [[Strand sort]]
* Non-comparison sorts
** [[Bead sort]]
** [[Bucket sort]]
** [[Burstsort]]: build a compact, cache efficient [[burst trie]] and then traverse it to create sorted output
** [[Counting sort]]
** [[Pigeonhole sort]]
** [[Postman sort]]: variant of Bucket sort which takes advantage of hierarchical structure
** [[Radix sort]]: sorts strings letter by letter
* Selection sorts
** [[Heapsort]]: convert the list into a heap, keep removing the largest element from the heap and adding it to the end of the list
** [[Selection sort]]: pick the smallest of the remaining elements, add it to the end of the sorted list
** [[Smoothsort]]
* Other
** [[Bitonic sorter]]
** [[Pancake sorting]]
** [[Spaghetti sort]]
** [[Topological sorting|Topological sort]]
* Unknown class
** [[Samplesort]]

====Subsequences====
{{further|Subsequence}}
* [[Longest common subsequence problem]]: Find the longest subsequence common to all sequences in a set of sequences
* [[Longest increasing subsequence problem]]: Find the longest increasing subsequence of a given sequence
* [[Ruzzo–Tompa algorithm]]: Find all non-overlapping, contiguous, maximal scoring subsequences in a sequence of real numbers
* [[Shortest common supersequence problem]]: Find the shortest supersequence that contains two or more sequences as subsequences

====Substrings====
{{further|Substrings}}
* [[Kadane's algorithm]]: finds the contiguous subarray with largest sum in an array of numbers
* [[Longest common substring problem]]: find the longest string (or strings) that is a substring (or are substrings) of two or more strings
* [[Substring search]]
** [[Aho–Corasick string matching algorithm]]: [[trie]] based algorithm for finding all substring matches to any of a finite set of strings
** [[Boyer–Moore string-search algorithm]]: amortized linear ([[sublinear]] in most times) algorithm for substring search
** [[Boyer–Moore–Horspool algorithm]]: Simplification of Boyer–Moore
** [[Knuth–Morris–Pratt algorithm]]: substring search which bypasses reexamination of matched characters
** [[Rabin–Karp string search algorithm]]: searches multiple patterns efficiently
** [[Zhu–Takaoka string matching algorithm]]: a variant of Boyer–Moore
* [[Ukkonen's algorithm]]: a [[linear-time]], [[online algorithm]] for constructing [[suffix tree]]s
* [[Matching wildcards]]
** [[InterNetNews|Rich Salz]]' [[wildmat]]: a widely used [[Open-source software|open-source]] [[recursion|recursive]] algorithm
** [[Krauss matching wildcards algorithm]]: an open-source non-recursive algorithm