This repository contains some more advanced algorithms for sorting, sorting in finite universes, searching and trees. For some algorithms there are short or more advanced tests.
Please see the appropriate file for the exact algorithm.
These implementations were done accompanying a masters lecture on algorithmics. Some of these algorithms are just implemented quick-and-dirty while others (2,3-tree) have gotten some more thought put into. I couldn't always find time.
None of the algorithms are fit and ready for production use. But most of them are available as robust implementations in standard or other libraries. Educational purpose only.
| Algorithm | Runtime |
|---|---|
| 2,3-tree (special case of the a,b-tree) | All operations in θ(logn) w.c. and a.c. |
| Algorithm | Runtime |
|---|---|
| Mergesort | O(n logn) |
| Quicksort | O(n^2) |
n = number of values
k = number of different values
s = max word length (Radixsort)
| Algorithm | Runtime |
|---|---|
| Countingsort | θ(n+k) w.c. and a.c. |
| Advanced Countingsort | θ(n+k) w.c. and a.c. |
| Bucketsort | θ(n+k) w.c. and a.c. |
| Radixsort | θ(s*(n+k)) w.c. and a.c. |
Searching for the n-th element in a not sorted list.
| Algorithm | Runtime |
|---|---|
| Randomised Algorithm | θ(n^2) w.c. θ(n) a.c. |
| Deterministic Algorithm | θ(n) w.c. and a.c. |
| Algorithm | Runtime |
|---|---|
| Binary Search | θ(logn) |
| Interpolation Search | θ(n) w.c. θ(log(logn)) a.c. |
| Quadratic Binary Search | θ(sqrt(n)) w.c. θ(log(logn)) a.c. |