A collection of Algorithms and Data structures implemented in dart.
This repository is intended for educational purposes, you could probably find more optimized implementations of the data structures and algorithms here described in the standard library or the collections package.
Most of the implementations in this repository can be further studied in the book Algorithms 4th edition .
- Bubble Sort
- Selection Sort
- Insertion Sort
- Shell Sort
- Merge Sort
- Quick Sort
- Heap Sort
| Algorithm | Stable | In Place | Running time | Extra space | Notes |
|---|---|---|---|---|---|
| Selection Sort | no | yes | n² | 1 | |
| Insertion sort | yes | yes | n - n² | 1 | Performs well if input is sorted |
| Shell Sort | no | yes | n*log(n)- n^(3/2) | 1 | |
| Quick Sort | no | yes | n*log(n) - n² | log(n) | Unlikely to hit worst case |
| 3 Way Quick sort | no | yes | n - n*log(n) | log(n) | Depends on distribution of keys |
| Merge Sort | yes | no | n*log(n) | n | |
| Heap Sort | no | yes | n*log(n) | 1 |
- Priority Queue
- Union Find
- Binary Search
- Quick Select
- Knuth-Morris-Pratt
We represent graphs most commonly either with adjacency matrices or adjacency lists.
For any graph given V vertices and E edges:
| Operation/Representation | Adjacency Matrix | Adjacency List |
|---|---|---|
| Edge between v and w | O(1) | O(deg(v)) |
| Neighbours | O(v) | O(deg(v)) |
| Space required | O(v²) | O(v+e) |
Degree(deg): The number of adjacent vertices of a given vertex.
Note Real-world graphs tend to be sparse so an adjacency list is most commonly used.
- Depth First Search (DFS)
- Breadth First Search (BFS)
- Topological Sort
- Cycle detection
- Strongly connected components (SCC)
- Dijkstra
- Bellman-Ford
- Edmonds-Karp
- A*
| Algorithm | Running time | Extra space | Notes |
|---|---|---|---|
| DFS | O(v+e) | O(v) | |
| BFS | O(v+e) | O(v) | |
| Topological sort | O(v+e) | O(v) | Requires no directed cycles |
| SCC | O(v+e) | O(v) | |
| Cycle detection | O(v+e) | O(v) | |
| Dijkstra | O(E*logV) | O(V) | Requires no negative weights or negative cycles |
| Bellman-Ford | O(E*V) | O(V) | Requires no negative cycles |
| Edmonds-Karp | O(V*E²) | O(V) |
To run all unit tests:
dart pub global activate very_good_cli
very_good test --coverageTo view the generated coverage report you can use lcov.
# Generate Coverage Report
genhtml coverage/lcov.info -o coverage/
# Open Coverage Report
open coverage/index.html