vshmyhlo/algorithms

Implementation of common algorithms and data structures

Misc

• Array Shuffle
• (WIP) Graham Scan (Convex Hull)
• (WIP) Union Find

Searching

• Binary Search
• Quick Select

Sorting

• Selection Sort
• Insertion Sort
• Shell Sort
• Heap Sort
• Merge Sort
• Quick Sort
• 3-Way Quick Sort

Containers

• Resizing Array
• Stack
• Queue
• Priority Queue
• Index Priority Queue
• Hash Map
• Binary Search Tree
• (Basic) Left-Leaning Red-Black Tree
• R-Way Trie
• Ternary Trie
• KD Tree
• (Basic) Interval Search Tree

Graphs

• Graph
• Directed Graph
• Edge Weighted Graph
• Edge Weighted Directed Graph
• Depth First Search
• Breadth First Search
• Connected Components
• Strong Connected Components
• Topological Sort
• Minimum Spanning Tree (Kruskal, Prim)
• Shortest Path (Dijkstra)

TODO

• AVL tree
• R-way Trie
• bipartite graph
• find cycle
• find cycle that uses each edge exactly once (euler cycle)
• render graph on a place without edges crossing

Intractable

• find cycle that uses each vertex exactly once (traveling salesman, hamilton cycle)
• check if two graphs identical except vertex names (graph isomorphism)