Please don't take effort to create pull requests for new algorithms or data structures. This is just a curiosity-driven personal hobby and was originally not intended to be a library. Feel free fork and modify to fit your need if that's what you are looking for. You can however open issues or fix bugs with pull requests, I would be happy to take a look when I get time

Various important computer science algorithms generically implemented in C#.

Install by nuget

For beta releases on beta branch

```
Install-Package Advanced.Algorithms -Pre
```

Not a stable release yet.

Supports

- .Net Standard 1.0 or above
- .Net Framework 4.0 or above

- Visual Studio Code as IDE for .NET core
- Visual Studio 2017 as IDE for .NET framework/.NET core

- Visual Studio Code as IDE for .NET core
- Visual Studio 2017 as IDE for Mono

- Visual Studio Code as IDE for .NET core
- Mono develop as IDE for Mono

- [X] Array list (dynamic array) (implementation | tests)
- [X] Skip list (implementation | tests)

- [X] HashSet (using separate chaining optionally with open address linear probing) (implementation | tests)
- [X] Ordered HashSet (implementation | tests)

- [X] Dictionary (using separate chaining optionally with open address linear probing) (implementation | tests)
- [X] Ordered Dictionary (implementation | tests)

- [X] Stack (using dynamic array and optionally using singly linked list) (implementation | tests)

- [X] Queue (using dynamic array and optionally using doubly linked list) (implementation | tests)
- [X] Priority queue (implementation | tests)

- [X] Singly linked list (implementation | tests)
- [X] Doubly linked list (implementation | tests)
- [X] Circular linked list (implementation | tests)

- [X] Binary heap (implementation | tests)
- [X] d-ary heap (implementation | tests)
- [X] Binomial heap (implementation | tests)
- [X] Fibonacci heap (implementation | tests)
- [X] Pairing heap (implementation | tests)

Note: It is observed that among the implementations here, in practice, with the exclusion of UpdateKey (decrement/increment) operation, regular Binary Heap & d-ary Heap outperforms other in theory superiors. Likely because it doesn't have pointer juggling overhead and hey arrays are faster!

- [X] Tree (implementation | tests)
- [X] Binary tree (implementation | tests)

- [X] Binary search tree (implementation | tests)
- [X] AVL tree (implementation | tests)
- [X] Red black tree (implementation | tests)
- [X] Splay tree (implementation | tests)
- [X] Treap tree (implementation | tests)

- [X] B-tree (implementation | tests)
- [X] B+ tree (implementation | tests)

- [X] Segment tree (implementation | tests)
- [X] Binary indexed tree (Fenwick tree) (implementation | tests)
- [X] Multi-dimensional interval tree (implementation | tests) using nested red-black tree
- [X] Multi-dimensional k-d tree (implementation | tests) for range and nearest neigbour queries
- [X] Multi-dimensional range tree (implementation | tests) using nested red-black tree
- [X] R-tree (implementation | tests)
- [X] Quadtree (implementation | tests)

TODO: Support multi-dimentional segment tree & binary indexed tree.

- [X] Prefix tree (Trie) (implementation | tests)
- [X] Suffix tree (implementation | tests)
- [X] Ternary search tree (implementation | tests)

TODO: implement trie compression.

- [X] Disjoint set (implementation | tests)
- [X] Sparse set (implementation | tests)
- [X] Bloom filter (implementation | tests)

- [X] Graph (implementation | tests)
- [X] Weighted Graph (implementation | tests)
- [X] DiGraph (implementation | tests)
- [X] Weighted DiGraph (implementation | tests)

- [X] Graph (implementation | tests)
- [X] Weighted Graph (implementation | tests)
- [X] DiGraph (implementation | tests)
- [X] Weighted DiGraph (implementation | tests)

- [X] Tarjan's articulation points finder (implementation | tests)

- [X] Tarjan's bridge finder (implementation | tests)

- [X] Kosaraju's strongly connected component finder (implementation | tests)
- [X] Tarjan's strongly connected component finder (implementation | tests)
- [X] Tarjan's bi-connected graph tester (implementation | tests)

- [X] M-coloring (implementation | tests)

- [X] Min vertex cover (implementation | tests)

- [X] Ford-Fulkerson algorithm (implementation | tests)
- [X] Edmonds Karp's improvement (implementation | tests) on Ford-Fulkerson algorithm
- [X] Push relabel algorithm (implementation | tests)

- [X] Bellman-Ford algorithm (implementation | tests)
- [X] Dijikstra's algorithm (implementation | tests) using Fibonacci heap.
- [X] Floyd-Warshall algorithm (implementation | tests)
- [X] Johnson's algorithm (implementation | tests)
- [X] Travelling salesman path (implementation | tests)
- [X] A* search algorithm (implementation | tests) using Fibonacci heap.

- [X] Max bipartite matching (implementation | tests) using Edmonds Karp's improved Ford Fulkerson max flow algorithm
- [X] Max bipartite matching (implementation | tests) using Hopcroft Karp algorithm

- [X] Minimum cut (implementation | tests) using Edmonds Karp's improved Ford Fulkerson max flow algorithm

- [X] Cycle detection (implementation | tests)

- [X] Depth first (implementation | tests)
- [X] Breadth first (implementation | tests)
- [X] Bi-directional (implementation | tests)

- [X] Depth first method (implementation | tests)
- [X] Kahn's algorithm (implementation | tests)

- [X] Kruskal's algorithm (implementation | tests) using merge sort and disjoint set
- [X] Prim's algorithm (implementation | tests)

- [X] Manacher's algorithm for linear time longest palindrome (implementation | tests)

- [X] Rabin-Karp string search (implementation | tests)
- [X] Knuth–Morris–Pratt (KMP) string search (implementation | tests)
- [X] Z algorithm for string search (implementation | tests)

- [X] Huffman coding (implementation | tests)

- [X] Binary search (implementation | tests)
- [X] Quick select for kth smallest/largest in unordered collection using median of medians (implementation | tests)
- [X] Majority element using Boyer-Moore voting algorithm (implementation | tests)

- [X] Bubble sort (implementation | tests)
- [X] Insertion sort (implementation | tests)
- [X] Selection sort (implementation | tests)
- [X] Shell sort (implementation | tests)
- [X] Tree sort (implementation | tests)
- [X] Quick sort (implementation | tests)
- [X] Heap sort (implementation | tests)
- [X] Merge sort (implementation | tests)
- [X] Bucket sort (implementation | tests)
- [X] Radix sort (implementation | tests)
- [X] Counting sort (implementation | tests)

Note: On a decent desktop, in given implementations here for +ive random input integers, the clear winner is counting sort (~0.1 seconds to sort 1 million integers) followed by Radix Sort (~0.4 seconds). Merge Sort, Heap Sort, Quick Sort & Bucket Sort are all winners for +ive & -ive random integer inputs. Tree sort has pointer juggling overhead on backing Red-Black Tree, so performs 8 times slower than Merge Sort in practice. Bubble Sort, Insertion Sort, Selection Sort & Shell Sort are among the worst for random input as observed from results.

- [X] Permutations (implementation | tests)
- [X] Combinations (implementation | tests)
- [X] Subsets (implementation | tests)

- [X] Circular queue (ring buffer) (implementation | tests)
- [X] Consistant hash (implementation | tests)
- [X] LRU cache (implementation | tests)
- [X] Asynchronous producer–consumer queue (implementation | tests)

- [X] Check primality (implementation | tests)
- [X] Generate primes using sieve of Eratosthenes (implementation | tests)
- [X] Fast exponentiation (implementation | tests)

- [X] Convex hull using gift wrapping algorithm (implementation | tests)
- [X] Line intersection (implementation | tests)
- [X] Closest point pair (implementation | tests)
- [X] Check if given point inside polygon (implementation | tests)
- [X] Rectangle intersection (implementation | tests)
- [X] Point rotation (implementation | tests)
- [X] Line interesections with Bentley-Ottmann sweep line algorithm using red-black tree and binary minimum heap (implementation | tests)

- [X] Base conversion (implementation | tests)
- [X] Calculate logarithm (base 2 & 10) (implementation | tests)
- [X] GCD (implementation | tests)

Get A Weekly Email With Trending Projects For These Topics

No Spam. Unsubscribe easily at any time.

c-sharp (12,487)

csharp (1,102)

algorithms (472)

data-structures (386)

graph-algorithms (79)

sorting-algorithms (58)

heap (37)