===== 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 | <code> T(n^2)  M(n) </code> | Vergleiche alle Elemente, von Anfang bin Hinten. Vergleiche jedes Element mit jedem.  | 
|Insertion sort | <code> T(n^2)  M(n) </code> | 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 | <code> T(n^2) </code> | 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 | <code> O(n^2) </code> | Crop the min Element by iterating all elements. Repeat, untill empty. | 
|Quick sort | <code> Bestcase: T(n log(n)) Average: T(n log(n))  Worst: T(n^2) </code> | 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 | <code> T(n log(n))  M(2*n). </code> | 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 | <code> </code> | Like selection sort, but using binary search trees (on the left are smaller elements, on the right are larger elements), not heaps.| 
|Heap sort | <code> Best= Worst = n*log(n) </code> | 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|