algorithms
Table of Contents
Algorithms and DataScructure
Datastructure
| List | Random Access | Tyical Usage | API |
|---|---|---|---|
| Queue | FIFO | Buffer | |
| Stack | LIFO | Iterative Algorithms | push(X) pop() |
| Heap (Prioritätsschlange) | HIFO (HighpriorityFirstOut) - there are two kind of heaps: min-heaps, where root nodes are allways larger, then their children. max-heaps, where root nodes are allways smaller than their children. | Sorting. | add(X) popMax() |
| Tree | Hierarchical | Search |
Sorting
It is known, that the best possible way to sort series of numbers (without additional knowledge about the initial ordering) O(n*log(n)) .
| Name | Big O | Algorithm |
|---|---|---|
| Bubble sort | T(n^2) M(n) | Vergleiche alle Elemente, von Anfang bin Hinten. Vergleiche jedes Element mit jedem. |
| Insertion sort | T(n^2) M(n) | Need two arrays. Take an unsorted element from the first, insert it on the rightplace into the second. Move all Elements in second list, if needed. |
| Count sort | T(n^2) | Führe eine count-liste. Vergleiche jedes ELement mit jedem. Addiere int der count-liste an der position des groesseren Elementes eine 1 dazu. <fc #FF0000>ACHTUNG:</fc> double memory usage. |
| Selection sort | O(n^2) | Crop the min Element by iterating all elements. Repeat, untill empty. |
| Quick sort | Bestcase: T(n log(n)) Average: T(n log(n)) Worst: T(n^2) | Suche ein ein Element R aus. Sortiere die Liste in zwei Teile, bez. R. Wende den Algorithmus auch fuer Teillisten mit Elementen kleiner & groeser R an. Fuege die Ergebisse zusammen. <fc #FF0000>ACHTUNG:</fc> The worst case is bad, but in practice on unsorted data - it works great. |
| Merge sort | T(n log(n)) M(2*n). | Separate the list into part lists of length n=1. Sort every part list. Merge part lists and use the partly sorted ordering, by taking the smallest header element from both of the lists you are merging. Do that for part lists lengths from n=1 to n=max |
| Tree sort | | Like selection sort, but using binary search trees (on the left are smaller elements, on the right are larger elements), not heaps. |
| Heap sort | Best= Worst = n*log(n) | Build a heap (e.g. in an array). Pop the highest element and restore the heap, by taking one of the leafs and sinking it, by swaping it with it's bigest child, until it has no children, which are larger. <fc #FF0000>Attention:The most efficient algorithm</fc> |
Search
Searching is done in balanced trees. The trees are binary trees, where
- the left child is smaller than parent,
- the right child is larger than parent
- the nodes have weighs, which reflect the probability, by which the node will be searched. <fc #FF0000>The sum of this weight, multiplied by distance from root is to be minimized, without loosing the sorted binary tree property.</fc>
Glossary
| German | English |
|---|---|
| O von f(n) | Big Oh of g of n |
| n hoch x | n to the power of x |
| n zum quadrat | n square |
algorithms.txt · Last modified: 2020/12/27 20:35 by 127.0.0.1