Classic Algorithms and Data Structures implemented in C++
Code written for practice. During my Master's degree in Computer Science at the University of Udine.
| Algorithm | Average Cost | Worst-case Cost |
|---|---|---|
| Insertion Sort | O(n^2) | O(n^2) |
| Merge Sort | ฮ(nlogn) | ฮ(nlogn) |
| QuickSort | O(nlogn) | O(n^2) |
| Counting Sort | O(n+k) | O(n+k) |
| Binary Search | O(logn) | O(logn) |
| Bubble Sort | O(n^2) | O(n^2) |
| Heapsort | O(nlogn) | O(nlogn) |
| Breadth-first Search (BFS) | O(|V|+|E|) | O(|V|+|E|) |
| Depth-first Search (DFS) | O(|V|+|E|) | O(|V|+|E|) |
| Prim (MST) | O(|E|log|V|) | O(|E|log|V|) |
| Kruskal (MST) | O(|E|log|V|) | O(|E|log|V|) |
| Bellman-Ford | O(|E||V|) | O(|E||V|) |
| Dijkstra | O(|E|+|V|log|V|) | O(|E|+|V|log|V|) |
| Maximum subarray (J.Kadane) | O(n) | O(n) |
| Data Structure | Methods |
|---|---|
| Linked list | insertFront(int value) - O(1), deleteFront() - O(1), isEmpty() - O(1) |
| Double Linked list | insertFront(int value) - O(1), deleteFront() - O(1) |
| Queue | enqueue(int value) - O(1), dequeue() - O(1), isEmpty() - O(1) |
| Stack | pop() - O(1), push() - O(1), top() - O(1), isEmpty() - O(1) |
| Binary Search Tree (BST) | insert(int value) - ฮ(logn), search(int value) - ฮ(logn), printInOrder() - ฮ(n), printPreOrder() - ฮ(n), printPostOrder() - ฮ(n) |
| Heap (binary max heap) | heapify(int index) - O(logn), insert(int value) - O(logn), deleteMax() - O(logn), buildHeap(vector<int> values) - O(n), heapSort() - O(nlogn) |
| Heap (binary min heap) | heapify(int index) - O(logn), insert(int value) - O(logn), deleteMin() - O(logn), buildHeap(vector<int> values) - O(n), heapSort() - O(nlogn) |
| Disjoint Set | makeSet() - ฮ(1), findSet() - ฮ(1), union() - ฮ(1) |
| Trie | add() - O(|string|), find() - O(|string|) |
Licensed under MIT.
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent