Algorithms and Datastructures
©
2015
/ Mario Konrad
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
Lists
Search
Sorting
Trees
Graph
- Graph
- Adjacency Matrix
- Adjacency List
- Shortest Path Dijkstra
- Depth First Search
- Breadth First Search
- Topological Sorting
- Minimum Spanning Tree
Geometry
Crypt / Cypher / Hash
Complexity
Big-O notation:
means: existance of c
elements of real number and the existance of n0
elements of natural numbers with for all
Axioms:
if in then
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:
- Number of compares: