Editing List of algorithms (section)

===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