The Algorithms in C++

These algorithms are the demonstration purposes only. There are many algorithms implementations in the C++ standard library that are much better for performance reasons. This project contains the following algorithms...

Allocators

| Name allocator | Allocation | Free | |:----------------------------------------:|:----------:|:----:| | Linear allocator | O(1) | - | | Pool allocator | O(1) | O(1) |

Caching

| Name algorithm | |:----------------------------------------:| | First in, first out (FIFO) | | Last recently used (LRU) |

Computational geometry

| Name algorithm | Average result | Worse result | |:----------------------------------------:|---------------:|:------------:| | Bresenham's line | - | - | | Ramer-Douglas-Peucker | O(nlog(n)) | O(n^2) | | Scan-line method | O(nlog(n)) | O(n*log(n)) |

Cryptography

| Name algorithm | |:----------------------------------------:| | Caesar cipher |

Data structures

| Name structure | Indexation | Search | Inserting | Deleting | Memory | |:------------------:|:-----------:|:--------------:|:------------:|:-----------:|:------:| | Binary Heap | - | - | O(log(n)) | O(log(n)) | O(n) | | Binary Tree | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) | | LinkedList | O(n) | O(n) | O(1) | O(1) | O(n) | | Queue | - | - | O(1) | O(1) | O(n) | | Stack | - | - | O(1) | O(1) | O(n) |

Dynamic programming

| Name algorithm | |:-----------------:| | Exchange of coins | | Fibonacci |

Graphs

| Name algorithm | |:--------------------------:| | Depth-First Search (DFS) | | Breadth-First Search (BFS) |

Multithreading

| Name algorithm | |:----------------------------------------:| | Ping Pong | | Producer and consumer |

Search

| Name algorithm | Data Structure | Average result | Worse result | |:-----------------:|:--------------:|:--------------:|:------------:| | Binary search | Sorted array | O(log(n)) | O(log(n)) | | Linear search | Array | O(n) | O(n) |

Set operations

| Name algorithm | |:----------------------------------------:| | Difference between the ordered sets | | Generation of all permutations from set | | Generation of all subsets of the set | | Intersection of the ordered sets | | Symmetric difference of ordered sets | | Union of the ordered sets |

SmartPointers

| Name pointer | |:----------------------------------------:| | Auto smart pointer | | Unique smart pointer | | Shared smart pointer |

Sorting

| Name algorithm |Data Structure | Best result | Average result | Worse result | |:-----------------:|:-------------:|:------------:|:--------------:|:------------:| | Bubble sorting | Array | O(n) | O(n^2) | O(n^2) | | Bucket sorting | Array | O(n) | O(n) | O(n^2) | | Counting sorting | Array | O(n) | O(n) | O(n) | | Insertion sorting | Array | O(n^2) | O(n^2) | O(n^2) | | Merge sorting | Array | O(nlog(n)) | O(nlog(n)) | O(nlog(n)) | | Quick sorting | Array | O(nlog(n)) | O(n*log(n)) | O(n^2) | | Selection sorting | Array | O(n) | O(n^2) | O(n^2) | | Shell sorting | Array | O(n^2) | O(n^2) | O(n^2) | | Stupid sorting | Array | O(n) | O(n^3) | O(n^3) |

Others

| Name algorithm | |:----------------------------:| | Euclidean algorithm | | Eratosthenes sieve | | Queens puzzle | | Maximum amound of subarrays | | Reversal of the forward list | | Tom Sawyer sence |

---

Other algorithms will be added later. Please follow the news.