Algorithms

Sorting Algorithms

Sorting Algorithm Comparison Table

Stable and Unstable Sorting

Stable Sorting Algorithms maintain the relative order of records with equal keys (a.k.a. values). Meaning, a sorting algorithm is stable if whenever there are two (2) records ‘R’ and ‘S’ with the same key and with ‘R’ appearing before ‘S’ in the original list, ‘R’ will appear before ‘S’ in the sorted list. Unstable Sorting Algorithms make no such guarantees. This being the only difference between stable and unstable sorting.

Comparison and Non-Comparison Based Sorting

Sorting algorithms are said to be comparison based if the method by which they decide to order elements is via a comparison operation and non-comparison based if the algorithm makes sorting decisions using some other means.

Insertion Sort

Selection Sort

Merge Sort

Counting Sort

Radix Sort

A radix a base for a representation of numbers. We could consider the base of the system that represents the numbers and the radix as being the same. The decimal system has base 10 and therefore the radix is also ten (10). There are ten (10) unique numbers that could appear in each digit’s place. Binary is base two (2) and therefore it’s radix is also two (2).

The sorting algorithm radix sort creates an array of all of the unique numbers representable in each digit, the radix, and sorts each set of digits. This auxiliary sorting algorithm must be stable so as to not undo the work that radix sort is doing (such as counting sort, merge sort, or timsort). Radix sort is a non-comparison based sorting algorithm and it starts with the most significant or the least significant digit and applies itself on each further set of digits in this set until it has sorted each place.

Time and Space Complexity (big-O)

Radix sort operates at O(n*w) time and O(w + n) space, where ’n’ is the number of values (a.k.a, keys) to sort and ‘w’ is the number of digits (a.k.a, the length of the values).

Searching Algorithms

Searching Algorithm Comparison Table

Graph Algorithms

Graph Algorithm Comparison Table

Misc Algorithms

C++ equivalent to python’s collections.Counter

python’s collections module has a Counter data structure that is essentially a associative array that keeps the count of each entry in an array.

#include <iostream>
#include <map>

int main() {
	std::map<std::string, int> counter;
	counter["dog"] = 8;
	counter["cat"]++;
	counter["cat"]++;
	counter["1"] = 0;

	for (auto pair : counter) {
		std::cout << pair.first << " : " << pair.second << std::endl;
	}
}

C++ print the keys-value pairs in a map

1. Using a range-based for-loop

The recommended approach in c++11 is to use the range-based for-loop for printing the key-value pairs in a std::map or std::unordered_map.

#include <iostream>
#include <unordered_map>

template<typename K, typename V>
void printMap(std::unordered_map<K,V> const &m) {
	for(auto const &pair : m) {
		std::cout << "{" << pair.second << ": " << pair.second << "}\n";
	}
}

int main() {
	std::unordered_map<int,char> m = {
		{1, 'A'},
		{2, 'B'},
		{3, 'C'}
	};

	printMap(m);
	return 0;
}

2. Using std::for_each function

Another simple solution is to use std::for_each, which takes an iterator to the beginning and end of the container structure (std::map, std::unordered_map, etc.) and applies a specified function on each pair within that range. The specified function ma be a unary function, lambda expression, or an object of a class that overloads operator().

#include <iostream>
#include <unordered_map>
#include <algorithm>

class MyClass {
	template<typename K, typesname V>
	void operator()(const std::pair<K,V> &p) {
		std::cout << "{" << p.first << ": " << p.second << "}\n";
	}
} obj;

template<typename K, typename V>
void print(const std::pair<K,V> &p) {
	std::cout << "{" << p.first << ": " << p.second << "}\n";
}

template<typename K, typename V>
void printMap(std::unordered_map const &m) {
	// Using a lambda expression
	std::for_each(m.begin(), m.end(), [](const std::pair<int,char> &p) {
		std::cout << "{" << p.first << ": " << p.second << "}\n";
	});

	// Or, pass an object of a class overloading the () operator
	// std::for_each(m.begin(), m.end(), obj);

	// Or, specify a function pointer.
	// std::for_ech(m.begin(), m.end(), print<K,V>);
}

int main() {
	std::unordered_map<int,char> m = {
		{1, 'A'},
		{2, 'B'},
		{3, 'C'}
	};

	printMap(m);
	return 0;
}

3. Using Iterators

This implementation uses iterators to a container (in this case a std::unordered_map) to print the key-value paris.

template<typename K, typename V>
void printMap(std::unordered_map<K,V> const &m) {
	for(auto itr = m.cbegin(), itr != m.cend(); ++itr) {
		std::cout << "{" << p.first << ": " << p.second << "}\n";
	}
}

int main() {
	std::unordered_map<int,char> m = {
		{1, 'A'},
		{2, 'B'},
		{3, 'C'}
	};

	printMap(m);
	return 0;
}

4. std::cout stream insertion specialization

We can specialize operator« for the std::ostream to handle printing the key-value pairs in a std::unordered_map. This is an extension of the range-based for-loop as it uses the same technique in the overload. This will allow for the use of std::cout to print the contents rather than calling a function to do so.

#include <iostream>
#include <unordered_map>

template<typename K, typename V>
std::ostream &operator<<(std::ostream &out, const std::unordered_map<K,V> &m) {
	for (const std::pair<K,V> &p : m) {
		out << "{" << p.first << ": " << p.second << "}\n";
	}
	return out;
}

int main() {
	std::unordered_map<int,char> m = {
		{1, 'A'},
		{2, 'B'},
		{3, 'C'}
	};

	std::cout << m;
	return 0;
}

Wave Function Collaps

• Fill this in

Diffusion (as in ai diffsion)

• Fill this in

Simulated Annealing

• Fill this in

Sleep Sort

• Fill this in

Quantom Bogo Sort

• Fill this in

Rivest-Shamir-Adleman (RSA) Cryptosystem

• Fill this in

Cracked on a quantum computer with Shor’s algorithm. Can be cracked on a smaller scale with quantum approximate optimization.

Marching Cubes

• Fill this in

Byzantine Fault Tolerance

• Fill this in

Solves the byzantine general problem

Boids

• Fill this in

Emergent behavior

Booyer-Moore String Search