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.

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.