## File: README.md ### List of Algorithms See our [directory](DIRECTORY.md) for easier navigation and a better overview of the project. ### Contributing Read through our [Contribution Guidelines](CONTRIBUTING.md) before you contribute. --- ## File: src/data_structures/README.md ### [B-Trees](./b_tree.rs) B-Trees are version of 2-3 trees, which are self-balancing. They are used to improve Disk reads and have a complexity of O(log(n)), for every tree operations.The number of Childrens/Keys a particular node has, is determined by the Branching Factor/Degree of that tree. B-Trees will always have sorted keys. - Branching Factor(B) / Degree (D): If B = n, n <= Children per Node < 2(n), n-1 <= Keys per Node < 2(n) - 1 __Properties__ * Worst/Average case performance for all operations O(log n) * Space complexity O(n) __Sources to read:__ * [Busying Oneself with B-Trees](https://medium.com/basecs/busying-oneself-with-b-trees-78bbf10522e7) * [Geeksforgeeks](https://www.geeksforgeeks.org/introduction-of-b-tree-2/) * [Rust API Docs](https://doc.rust-lang.org/std/collections/struct.BTreeMap.html) * [Keon Algorithms](https://github.com/keon/algorithms) * [MIT Open Course](https://www.youtube.com/watch?v=TOb1tuEZ2X4) ### [AVL Tree](./avl_tree.rs) An AVL Tree is a self-balancing binary search tree. The heights of any two sibling nodes must differ by at most one; the tree may rebalance itself after insertion or deletion to uphold this property. __Properties__ * Worst/Average time complexity for basic operations: O(log n) * Worst/Average space complexity: O(n) __Sources to read:__ * [Wikipedia](https://en.wikipedia.org/wiki/AVL_tree) * Geeksforgeeks ([Insertion](https://www.geeksforgeeks.org/avl-tree-set-1-insertion), [Deletion](https://www.geeksforgeeks.org/avl-tree-set-2-deletion)) ### [Doubly linked list](./linked_list.rs) ![alt text][doubly-linked-list] A linked list is also a `linear` data structure, and each element in the linked list is actually a separate object while all the objects are `linked together by the reference filed` in each element. In a `doubly linked list`, each node contains, besides the `next` node link, a second link field pointing to the `previous` node in the sequence. The two links may be called `next` and `prev`. And many modern operating systems use doubly linked lists to maintain references to active processes, threads and other dynamic objects. __Properties__ * Indexing O(n) * Insertion O(1) * Beginning O(1) * Middle (Indexing time+O(1)) * End O(n) * Deletion O(1) * Beginning O(1) * Middle (Indexing time+O(1)) * End O(n) * Search O(n) __Source to read:__ * [Wikipedia](https://en.wikipedia.org/wiki/Linked_list) * [LeetCode](https://leetcode.com/explore/learn/card/linked-list/) * [Brilliant](https://brilliant.org/wiki/linked-lists/) * [Rust API Docs](https://doc.rust-lang.org/std/collections/struct.LinkedList.html) ### [Stack Using Singly Linked List](./stack_using_singly_linked_list.rs) ![][stack] From Wikipedia, a stack is an abstract data type that serves as a collection of elements, with two main principal operations, `Push` and `Pop`. __Properties__ * Push O(1) * Pop head.data O(1) tail.data O(n) * Peek O(1) __Source to read:__ * [Wikipedia](https://en.wikipedia.org/wiki/Linked_list) * [rust-unofficial](https://rust-unofficial.github.io/too-many-lists/index.html) * [Stack Implementation and complexity](https://medium.com/@kaichimomose/stack-implementation-and-complexity-c176924e6a6b) [doubly-linked-list]: https://upload.wikimedia.org/wikipedia/commons/thumb/5/5e/Doubly-linked-list.svg/610px-Doubly-linked-list.svg.png [stack]: https://upload.wikimedia.org/wikipedia/commons/thumb/b/b4/Lifo_stack.png/700px-Lifo_stack.png --- ## File: src/ciphers/README.md ## Ciphers ### [Caesar](./caesar.rs) ![alt text][caesar] In cryptography, a **Caesar cipher**, also known as Caesar's cipher, the shift cipher, Caesar's code or Caesar shift, is one of the simplest and most widely known encryption techniques. It is **a type of substitution cipher** in which each letter in the plaintext is replaced by a letter some fixed number of positions down the alphabet. For example, with a left shift of 3, D would be replaced by A, E would become B, and so on. The method is named after **Julius Caesar**, who used it in his private correspondence. The encryption step performed by a Caesar cipher is often incorporated as part of more complex schemes, such as the Vigenère cipher, and still has modern application in the ROT13 system. As with all single-alphabet substitution ciphers, the Caesar cipher is easily broken and in modern practice offers essentially no communication security. ###### Source: [Wikipedia](https://en.wikipedia.org/wiki/Caesar_cipher) ### [Polybius](./polybius.rs) The **Polybius square**, also known as the Polybius checkerboard, is a device invented by the ancient Greeks Cleoxenus and Democleitus, and made famous by the historian and scholar Polybius. The device is used for fractionating plaintext characters so that they can be represented by a smaller set of symbols, which is useful for telegraphy, steganography, and cryptography. The **Polybius square** is also used as a basic cipher called the Polybius cipher. This cipher is a **substitution cipher** with characters being substituted for pairs of digits. #### Example cipher Δ | 1 | 2 | 3 | 4 | 5 ---|---|---|---| --- |--- 1 | a | b | c | d | e 2 | f | g | h | i/j | k 3 | l | m | n | o | p 4 | q | r | s | t | u 5 | v | w | x | y | z ###### Source: [Wikipedia](https://en.wikipedia.org/wiki/Polybius_square) ### [Vigenère](./vigenere.rs) The **Vigenère cipher** is a method of encrypting alphabetic text by using a series of **interwoven Caesar ciphers** based on the letters of a keyword. It is **a form of polyalphabetic substitution**. The Vigenère cipher has been reinvented many times. The method was originally described by Giovan Battista Bellaso in his 1553 book La cifra del. Sig. Giovan Battista Bellaso; however, the scheme was later misattributed to Blaise de Vigenère in the 19th century, and is now widely known as the "Vigenère cipher". Though the cipher is easy to understand and implement, for three centuries it resisted all attempts to break it; this earned it the description **le chiffre indéchiffrable**(French for 'the indecipherable cipher'). Many people have tried to implement encryption schemes that are essentially Vigenère ciphers. Friedrich Kasiski was the first to publish a general method of deciphering a Vigenère cipher in 1863. ###### Source: [Wikipedia](https://en.wikipedia.org/wiki/Vigen%C3%A8re_cipher) ### [SHA-2](./sha256.rs) SHA-2 (Secure Hash Algorithm 2) is a set of cryptographic hash functions designed by the United States National Security Agency (NSA) and first published in 2001. They are built using the Merkle–Damgård structure, from a one-way compression function itself built using the Davies–Meyer structure from a (classified) specialized block cipher. ###### Source: [Wikipedia](https://en.wikipedia.org/wiki/SHA-2) ### [Transposition](./transposition.rs) In cryptography, a **transposition cipher** is a method of encryption by which the positions held by units of plaintext (which are commonly characters or groups of characters) are shifted according to a regular system, so that the ciphertext constitutes a permutation of the plaintext. That is, the order of the units is changed (the plaintext is reordered). Mathematically a bijective function is used on the characters' positions to encrypt and an inverse function to decrypt. ###### Source: [Wikipedia](https://en.wikipedia.org/wiki/Transposition_cipher) [caesar]: https://upload.wikimedia.org/wikipedia/commons/4/4a/Caesar_cipher_left_shift_of_3.svg ### [AES](./aes.rs) The Advanced Encryption Standard (AES), also known by its original name Rijndael (Dutch pronunciation: [ˈrɛindaːl]), is a specification for the encryption of electronic data established by the U.S. National Institute of Standards and Technology (NIST) in 2001. ###### Source: [Wikipedia](https://en.wikipedia.org/wiki/Advanced_Encryption_Standard) --- ## File: src/searching/README.md ## Search Algorithms ### [Linear](./linear_search.rs) ![alt text][linear-image] From [Wikipedia][linear-wiki]: linear search or sequential search is a method for finding a target value within a list. It sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched. Linear search runs in at worst linear time and makes at most n comparisons, where n is the length of the list. __Properties__ * Worst case performance O(n) * Best case performance O(1) * Average case performance O(n) * Worst case space complexity O(1) iterative ### [Binary](./binary_search.rs) ![alt text][binary-image] From [Wikipedia][binary-wiki]: Binary search, also known as half-interval search or logarithmic search, is a search algorithm that finds the position of a target value within a sorted array. It compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful. __Properties__ * Worst case performance O(log n) * Best case performance O(1) * Average case performance O(log n) * Worst case space complexity O(1) ### [Exponential](./exponential_search.rs) ![alt text][exponential-image] From [Wikipedia][exponential-wiki]: Exponential search allows for searching through a sorted, unbounded list for a specified input value (the search "key"). The algorithm consists of two stages. The first stage determines a range in which the search key would reside if it were in the list. In the second stage, a binary search is performed on this range. In the first stage, assuming that the list is sorted in ascending order, the algorithm looks for the first exponent, j, where the value 2^j is greater than the search key. This value, 2^j becomes the upper bound for the binary search with the previous power of 2, 2^(j - 1), being the lower bound for the binary search. __Properties__ * Worst case performance O(log i) * Best case performance O(1) * Average case performance O(log i) * Worst case space complexity O(1) ### [Jump](./jump_search.rs) ![alt text][jump-image] From [Wikipedia][jump-wiki]: In computer science, a jump search or block search refers to a search algorithm for ordered lists. It works by first checking all items L(km), where k ∈ N and m is the block size, until an item is found that is larger than the search key. To find the exact position of the search key in the list a linear search is performed on the sublist L[(k-1)m, km]. __Properties__ * Worst case performance O(√n) * Best case performance O(1) * Average case performance O(√n) * Worst case space complexity O(1) ### [Fibonacci](./fibonacci_search.rs) From [Wikipedia][fibonacci-wiki]: In computer science, the Fibonacci search technique is a method of searching a sorted array using a divide and conquer algorithm that narrows down possible locations with the aid of Fibonacci numbers. Compared to binary search where the sorted array is divided into two equal-sized parts, one of which is examined further, Fibonacci search divides the array into two parts that have sizes that are consecutive Fibonacci numbers. __Properties__ * Worst case performance O(log n) * Best case performance O(1) * Average case performance O(log n) * Worst case space complexity O(1) [linear-wiki]: https://en.wikipedia.org/wiki/Linear_search [linear-image]: http://www.tutorialspoint.com/data_structures_algorithms/images/linear_search.gif [binary-wiki]: https://en.wikipedia.org/wiki/Binary_search_algorithm [binary-image]: https://upload.wikimedia.org/wikipedia/commons/f/f7/Binary_search_into_array.png [exponential-wiki]: https://en.wikipedia.org/wiki/Exponential_search [exponential-image]: https://upload.wikimedia.org/wikipedia/commons/4/45/Exponential_search.svg [jump-wiki]: https://en.wikipedia.org/wiki/Jump_search [jump-image]: https://static.studytonight.com/data-structures/images/Jump%20Search%20technique.PNG [fibonacci-wiki]: https://en.wikipedia.org/wiki/Fibonacci_search_technique --- ## File: src/sorting/README.md ## Sort Algorithms ### [Bogo-sort](./bogo_sort.rs) ![alt text][bogo-image] From [Wikipedia][bogo-wiki]: In computer science, bogosort is a sorting algorithm based on the generate and test paradigm. The function successively generates permutations of its input until it finds one that is sorted. It is not considered useful for sorting, but may be used for educational purposes, to contrast it with more efficient algorithms. __Properties__ * Worst case performance (unbounded in randomized version) * Best case performance O(n) * Average case performance O((n+1)!) ### [Bubble](./bubble_sort.rs) ![alt text][bubble-image] From [Wikipedia][bubble-wiki]: Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. __Properties__ * Worst case performance O(n^2) * Best case performance O(n) * Average case performance O(n^2) ###### View the algorithm in [action][bubble-toptal] ### [Cocktail-Shaker](./cocktail_shaker_sort.rs) ![alt text][shaker-image] From [Wikipedia][shaker-wiki]: Cocktail shaker sort, also known as bidirectional bubble sort, cocktail sort, shaker sort (which can also refer to a variant of selection sort), ripple sort, shuffle sort, or shuttle sort, is an extension of bubble sort. The algorithm extends bubble sort by operating in two directions. While it improves on bubble sort by more quickly moving items to the beginning of the list, it provides only marginal performance improvements. __Properties__ * Worst case performance O(n^2) * Best case performance O(n) * Average case performance O(n^2) ### [Comb-sort](./comb_sort.rs) ![comb sort][comb-sort] From [wikipedia][comb-sort-wiki]: Comb sort is a relatively simple sorting algorithm and improves on bubble sort in the same way that shell sort improves on insertion sort. The basic idea of comb sort is that the gap(distance from two compared elements) can be much more than 1. And the inner loop of bubble sort, which does actual `swap`, is modified such that the gap between swapped elements goes down in steps of a `shrink factor k: [n/k, n/k^2, ..., 1]`. And the gap is divided by the shrink factor in every loop, and the process repeats until the gap is 1. At this point, comb sort continues using a gap of 1 until the list is fully sorted. The final stage of the sort is thus equivalent to a bubble sort, but this time most turtles have been dealt with, so a bubble sort will be efficient. And the shrink factor has a great effect on the efficiency of comb sort and `k=1.3` has been suggested as an ideal value. __Properties__ * Worst case performance O(n^2) * Best case performance O(n log n) * Average case performance O(n^2/2^p) where `p` is the number of increments. ### [Counting](./counting_sort.rs) From [Wikipedia][counting-wiki]: In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence. Its running time is linear in the number of items and the difference between the maximum and minimum key values, so it is only suitable for direct use in situations where the variation in keys is not significantly greater than the number of items. However, it is often used as a subroutine in another sorting algorithm, radix sort, that can handle larger keys more efficiently. __Properties__ * Worst case performance O(n+k) * Best case performance O(n+k) * Average case performance O(n+k), where n is the number of integers to sort and k is the difference between the largest and smallest integer in our list. ### [Insertion](./insertion_sort.rs) ![alt text][insertion-image] From [Wikipedia][insertion-wiki]: Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. __Properties__ * Worst case performance O(n^2) * Best case performance O(n) * Average case performance O(n^2) ###### View the algorithm in [action][insertion-toptal] ### [Gnome](./gnome_sort.rs) ![alt text][gnome-image] From [Wikipedia][gnome-wiki]: The gnome sort is a sorting algorithm which is similar to insertion sort in that it works with one item at a time but gets the item to the proper place by a series of swaps, similar to a bubble sort. It is conceptually simple, requiring no nested loops. The average running time is O(n^2) but tends towards O(n) if the list is initially almost sorted __Properties__ * Worst case performance O(n^2) * Best case performance O(n) * Average case performance O(n^2) ### [Merge](./merge_sort.rs) ![alt text][merge-image] From [Wikipedia][merge-wiki]: In computer science, merge sort (also commonly spelled mergesort) is an efficient, general-purpose, comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Mergesort is a divide and conquer algorithm that was invented by John von Neumann in 1945. __Properties__ * Worst case performance O(n log n) * Best case performance O(n log n) * Average case performance O(n log n) ###### View the algorithm in [action][merge-toptal] ### [Odd-even](./odd_even_sort.rs) ![alt text][odd-even-image] From [Wikipedia][odd-even-wiki]: In computing, an odd–even sort or odd–even transposition sort (also known as brick sort or parity sort) is a relatively simple sorting algorithm, developed originally for use on parallel processors with local interconnections. It is a comparison sort related to bubble sort, with which it shares many characteristics. It functions by comparing all odd/even indexed pairs of adjacent elements in the list and, if a pair is in the wrong order (the first is larger than the second) the elements are switched. The next step repeats this for even/odd indexed pairs (of adjacent elements). Then it alternates between odd/even and even/odd steps until the list is sorted. NOTE: The implementation is an adaptation of the algorithm for a single-processor machine, while the original algorithm was devised to be executed on many processors simultaneously. __Properties__ * Worst case performance O(n^2) * Best case performance O(n) * Average case performance O(n^2) ### [Pancake](./pancake_sort.rs) ![alt text][pancake-image] From [Wikipedia][pancake-wiki]: All sorting methods require pairs of elements to be compared. For the traditional sorting problem, the usual problem studied is to minimize the number of comparisons required to sort a list. The number of actual operations, such as swapping two elements, is then irrelevant. For pancake sorting problems, in contrast, the aim is to minimize the number of operations, where the only allowed operations are reversals of the elements of some prefix of the sequence. Now, the number of comparisons is irrelevant. ### [Quick](./quick_sort.rs) ![alt text][quick-image] From [Wikipedia][quick-wiki]: Quicksort (sometimes called partition-exchange sort) is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order. __Properties__ * Worst case performance O(n^2) * Best case performance O(n log n) or O(n) with three-way partition * Average case performance O(n log n) ###### View the algorithm in [action][quick-toptal] ### [Radix](./radix_sort.rs) ![alt text][radix-image] From [Wikipedia][radix-wiki]: Radix sort is a non-comparative sorting algorithm. It avoids comparison by creating and distributing elements into buckets according to their radix. For elements with more than one significant digit, this bucketing process is repeated for each digit, while preserving the ordering of the prior step, until all digits have been considered. __Properties__ * Worst case performance O(w*n) where w is the number of bits required to store each key. ### [Selection](./selection_sort.rs) ![alt text][selection-image] From [Wikipedia][selection-wiki]: The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right. __Properties__ * Worst case performance O(n^2) * Best case performance O(n^2) * Average case performance O(n^2) ###### View the algorithm in [action][selection-toptal] ### [Shell](./shell_sort.rs) ![alt text][shell-image] From [Wikipedia][shell-wiki]: Shellsort is a generalization of insertion sort that allows the exchange of items that are far apart. The idea is to arrange the list of elements so that, starting anywhere, considering every nth element gives a sorted list. Such a list is said to be h-sorted. Equivalently, it can be thought of as h interleaved lists, each individually sorted. __Properties__ * Worst case performance O(nlog2 2n) * Best case performance O(n log n) * Average case performance depends on gap sequence ###### View the algorithm in [action][shell-toptal] ### [Stooge](./stooge_sort.rs) ![alt text][stooge-image] From [Wikipedia][stooge-wiki]: Stooge sort is a recursive sorting algorithm. It is notable for its exceptionally bad time complexity of O(n^(log 3 / log 1.5)) = O(n^2.7095...). The running time of the algorithm is thus slower compared to reasonable sorting algorithms, and is slower than Bubble sort, a canonical example of a fairly inefficient sort. It is however more efficient than Slowsort. The name comes from The Three Stooges. __Properties__ * Worst case performance O(n^(log(3) / log(1.5))) ### [Tim](./tim_sort.rs) ![alt text][tim-image] From [Wikipedia][tim-wiki]: Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It was implemented by Tim Peters in 2002 for use in the Python programming language. The algorithm finds subsequences of the data that are already ordered (runs) and uses them to sort the remainder more efficiently. This is done by merging runs until certain criteria are fulfilled. Timsort has been Python's standard sorting algorithm since version 2.3. It is also used to sort arrays of non-primitive type in Java SE 7, on the Android platform, in GNU Octave, on V8, Swift, and Rust. __Properties__ * Worst-case performance O(max element size(ms)) * Best-case performance O(max element size(ms)) ### [Sleep](./sleep_sort.rs) ![alt text][sleep-image] From [Wikipedia][bucket-sort-wiki]: This is an idea that was originally posted on the message board 4chan, replacing the bucket in bucket sort with time instead of memory space. It is actually possible to sort by "maximum of all elements x unit time to sleep". The only case where this would be useful would be in examples. ### [Patience](./patience_sort.rs) [patience-video] From [Wikipedia][patience-sort-wiki]: The algorithm's name derives from a simplified variant of the patience card game. The game begins with a shuffled deck of cards. The cards are dealt one by one into a sequence of piles on the table, according to the following rules. 1. Initially, there are no piles. The first card dealt forms a new pile consisting of the single card. 2. Each subsequent card is placed on the leftmost existing pile whose top card has a value greater than or equal to the new card's value, or to the right of all of the existing piles, thus forming a new pile. 3. When there are no more cards remaining to deal, the game ends. This card game is turned into a two-phase sorting algorithm, as follows. Given an array of n elements from some totally ordered domain, consider this array as a collection of cards and simulate the patience sorting game. When the game is over, recover the sorted sequence by repeatedly picking off the minimum visible card; in other words, perform a k-way merge of the p piles, each of which is internally sorted. __Properties__ * Worst case performance O(n log n) * Best case performance O(n) [bogo-wiki]: https://en.wikipedia.org/wiki/Bogosort [bogo-image]: https://upload.wikimedia.org/wikipedia/commons/7/7b/Bogo_sort_animation.gif [bubble-toptal]: https://www.toptal.com/developers/sorting-algorithms/bubble-sort [bubble-wiki]: https://en.wikipedia.org/wiki/Bubble_sort [bubble-image]: https://upload.wikimedia.org/wikipedia/commons/thumb/8/83/Bubblesort-edited-color.svg/220px-Bubblesort-edited-color.svg.png "Bubble Sort" [shaker-wiki]: https://en.wikipedia.org/wiki/Cocktail_shaker_sort [shaker-image]: https://upload.wikimedia.org/wikipedia/commons/e/ef/Sorting_shaker_sort_anim.gif [counting-wiki]: https://en.wikipedia.org/wiki/Counting_sort [insertion-toptal]: https://www.toptal.com/developers/sorting-algorithms/insertion-sort [insertion-wiki]: https://en.wikipedia.org/wiki/Insertion_sort [insertion-image]: https://upload.wikimedia.org/wikipedia/commons/7/7e/Insertionsort-edited.png "Insertion Sort" [gnome-wiki]: https://en.wikipedia.org/wiki/Gnome_sort [gnome-image]: https://upload.wikimedia.org/wikipedia/commons/3/37/Sorting_gnomesort_anim.gif "Insertion Sort" [pancake-wiki]: https://en.wikipedia.org/wiki/Pancake_sorting [pancake-image]: https://upload.wikimedia.org/wikipedia/commons/0/0f/Pancake_sort_operation.png [quick-toptal]: https://www.toptal.com/developers/sorting-algorithms/quick-sort [quick-wiki]: https://en.wikipedia.org/wiki/Quicksort [quick-image]: https://upload.wikimedia.org/wikipedia/commons/6/6a/Sorting_quicksort_anim.gif "Quick Sort" [merge-toptal]: https://www.toptal.com/developers/sorting-algorithms/merge-sort [merge-wiki]: https://en.wikipedia.org/wiki/Merge_sort [merge-image]: https://upload.wikimedia.org/wikipedia/commons/c/cc/Merge-sort-example-300px.gif "Merge Sort" [odd-even-image]: https://upload.wikimedia.org/wikipedia/commons/1/1b/Odd_even_sort_animation.gif [odd-even-wiki]: https://en.wikipedia.org/wiki/Odd%E2%80%93even_sort [radix-wiki]: https://en.wikipedia.org/wiki/Radix_sort [radix-image]: https://ds055uzetaobb.cloudfront.net/brioche/uploads/IEZs8xJML3-radixsort_ed.png?width=400 "Radix Sort" [selection-toptal]: https://www.toptal.com/developers/sorting-algorithms/selection-sort [selection-wiki]: https://en.wikipedia.org/wiki/Selection_sort [selection-image]: https://upload.wikimedia.org/wikipedia/commons/thumb/b/b0/Selection_sort_animation.gif/250px-Selection_sort_animation.gif "Selection Sort Sort" [shell-toptal]: https://www.toptal.com/developers/sorting-algorithms/shell-sort [shell-wiki]: https://en.wikipedia.org/wiki/Shellsort [shell-image]: https://upload.wikimedia.org/wikipedia/commons/d/d8/Sorting_shellsort_anim.gif "Shell Sort" [stooge-image]: https://upload.wikimedia.org/wikipedia/commons/f/f8/Sorting_stoogesort_anim.gif [stooge-wiki]: https://en.wikipedia.org/wiki/Stooge_sort [tim-image]: https://thumbs.gfycat.com/BruisedFrigidBlackrhino-size_restricted.gif [tim-wiki]: https://en.wikipedia.org/wiki/Timsort [comb-sort]: https://upload.wikimedia.org/wikipedia/commons/4/46/Comb_sort_demo.gif [comb-sort-wiki]: https://en.wikipedia.org/wiki/Comb_sort [sleep-sort]: [sleep-sort-wiki]: https://ja.m.wikipedia.org/wiki/バケットソート#.E3.82.B9.E3.83.AA.E3.83.BC.E3.83.97.E3.82.BD.E3.83.BC.E3.83.88 [patience-sort-wiki]: https://en.wikipedia.org/wiki/Patience_sorting [patience-video]: https://user-images.githubusercontent.com/67539676/212542208-d3f7a824-60d8-467c-8097-841945514ae9.mp4 --- ## File: src/string/README.md ## String Algorithms ### [Aho-Corasick Algorithm](./aho_corasick.rs) From [Wikipedia][aho-corasick-wiki]: a string-searching algorithm invented by Alfred V. Aho and Margaret J. Corasick in 1975.[1] It is a kind of dictionary-matching algorithm that locates elements of a finite set of strings (the "dictionary") within an input text. It matches all strings simultaneously. [aho-corasick-wiki]: https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm ### [Burrows-Wheeler transform](./burrows_wheeler_transform.rs) From [Wikipedia][burrows-wheeler-wiki]: The Burrows–Wheeler transform (BWT, also called block-sorting compression) rearranges a character string into runs of similar characters. This is useful for compression, since it tends to be easy to compress a string that has runs of repeated characters by techniques such as move-to-front transform and run-length encoding. More importantly, the transformation is reversible, without needing to store any additional data except the position of the first original character. The BWT is thus a "free" method of improving the efficiency of text compression algorithms, costing only some extra computation. __Properties__ * Worst-case performance O(n) [burrows-wheeler-wiki]: https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform ### [Knuth Morris Pratt](./knuth_morris_pratt.rs) From [Wikipedia][kmp-wiki]: searches for occurrences of a "word" W within a main "text string" S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters. Knuth Morris Pratt search runs in linear time in the length of W and S. __Properties__ * Case performance O(s + w) * Case space complexity O(w) [kmp-wiki]: https://en.wikipedia.org/wiki/Knuth–Morris–Pratt_algorithm ### [Manacher](./manacher.rs) From [Wikipedia][manacher-wiki]: find a longest palindrome in a string in linear time. __Properties__ * Worst-case time complexity is O(n) * Worst-case space complexity is O(n) [manacher-wiki]: https://en.wikipedia.org/wiki/Longest_palindromic_substring#Manacher's_algorithm ### [Rabin Karp](./rabin_karp.rs) From [Wikipedia][rabin-karp-wiki]: a string-searching algorithm created by Richard M. Karp and Michael O. Rabin that uses hashing to find an exact match of a pattern string in a text. [rabin-karp-wiki]: https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm ### [Hamming Distance](./hamming_distance.rs) From [Wikipedia][hamming-distance-wiki]: In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of substitutions required to change one string into the other, or the minimum number of errors that could have transformed one string into the other. In a more general context, the Hamming distance is one of several string metrics for measuring the edit distance between two sequences. It is named after the American mathematician Richard Hamming. [run-length-encoding-wiki]: https://en.wikipedia.org/wiki/Run-length_encoding ### [Run Length Encoding](./run_length_encoding.rs) From [Wikipedia][run-length-encoding-wiki]: a form of lossless data compression in which runs of data (sequences in which the same data value occurs in many consecutive data elements) are stored as a single data value and count, rather than as the original run. [hamming-distance-wiki]: https://en.wikipedia.org/wiki/Hamming_distance