Just a safe java repo for some geek experiences
I have created a setup to test and compare multiple Sorting Algorithms. They have been built with simplicity in mind, for the sake of readability
Standard Implementations 😫 (Boring versions, only used for elementary school to teach kids how to sort and array)
| Algorithm | Time complexity | Space complexity | Is Recursive | Notes |
|---|---|---|---|---|
| Quick Sort | O(n * log n) | O(log n) | ✅ | |
| Merge Sort | O(n * log n) | O(n) | ✅ | Stable |
| Heap Sort | O(n * log n) | O(1) | ✅ | Not Stable |
| Buble Sort | O(n^2) | O(1) | ❌ | 🐌 Stable 🐌 |
- n -> Array size
Only non recursive and "stable" algorithms are welcomed here. If you can't hold big dick arrays without causing stack overflow so please leave now.
| Algorithm | Time complexity | Space complexity | Is Recursive | Notes |
|---|---|---|---|---|
| Quick Sort Random pivot | O(n * log n) | O(n) | ❌ | |
| Quick Sort + Selection Sort with threshold | O(n * log n) | O(n) | ❌ | |
| Parallel Merge Sort | O(n * log n) | O(n) | ❌ | |
| Internal Java Array Sorting implementation | ---- | ---- | ---- | Uses a quickSort dual pivot, tuned to the bone , I plan to dissect this sorting algorithm later |
| Algorithm | Time complexity | Space complexity | Is Recursive | Notes |
|---|---|---|---|---|
| Breadth First Search (aka BFS) | O(V + E) | O(V) | ❌ | Auxiliary structure: Queue |
| Depth-first traversal (aka DFS) | O(V + E) | O(V) | ❌ | Auxiliary structure: Stack |
- v -> Vertices
- e -> Edges
This is not a benchmark, for that multiple consecutive runs are mandatory to obtain a precise measure to avoid any JIT compile suprises