programming / C++ / sailing / nerd stuff
Algorithms and Datastructures

This section is about algorithms and data structures. Examples are given, implemented mostly in C++ (C++11). Algorithms are probably implemented somewhere else as well (e.g. standard c++ library, etc.). This page just shows how such algorithms could be implemented.

## Algorithms

### Graph

• Graph
• Shortest Path Dijkstra
• Depth First Search
• Topological Sorting
• Minimum Spanning Tree

## Complexity

Big-O notation: $O(n)$

$f(n) = O(g(n))$ means: existance of c elements of real number and the existance of n0 elements of natural numbers with $f(n)<= c * round(g(n))$ for all $n > n0$

Axioms:

• $O(k * f(n)) = O(fn(n))$
• $O(f(n)) * O(g(n)) = O(f(n) * g(n))$
• $O(f(n) + g(n)) = O(f(n))$

if $\lim_{n\rightarrow\infty}\frac{g}{f}$ in $\mathbb{R}$ then

• $O(log2(n)) = O(ln(n))$

## Definitions for Sorting

• Internal Sorting: Everything in main memory. Random access to all elements.
• External Sorting: Data on extenal memory (ex: file, linked list, etc.).
• Stability: An algorithm is stable if the order of elements with equal key keeps the same after sorting.
• Indirect Sorting: An array of vectors is sorted, not the records with data itself.
• Number of moves/swaps: $M$
• Number of compares: $C$