Advanced_Algorithms
Advanced_Algorithms copied to clipboard
MauriceGit
Quick implementations of some advanced algorithms for searching, sorting and trees
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. |
Metadata
Owner
MauriceGit
Metadata
Quick implementations of some advanced algorithms for searching, sorting and trees