MauriceGit / Advanced_algorithms
Programming Languages
Advanced Algorithms
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.
Tree
| Algorithm | Runtime |
|---|---|
| 2,3-tree (special case of the a,b-tree) | All operations in θ(logn) w.c. and a.c. |
General Sorting
| Algorithm | Runtime |
|---|---|
| Mergesort | O(n logn) |
| Quicksort | O(n^2) |
Sorting in finite domains
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. |
Order statistics (Select algorithms)
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. |
Searching in sorted Arrays
| 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. |