#include <iostream>
#include <vector>

template<class RandomIt, class Consumer>
void my_for_each(RandomIt comeco, RandomIt fim, Consumer faz_algo) {
	for (RandomIt it = comeco; it != fim; it++) {
		faz_algo(*it);
	}
}

template<class RandomIt, class Comparador>
void insertionsort(RandomIt comeco, RandomIt fim, Comparador cmp) {
	for (RandomIt it = comeco + 1; it != fim ; it++) {
		for (RandomIt it2 = it; it2 != comeco; it2--) {
			RandomIt prev = it2 - 1;
			if (cmp(*it2, *prev)) {
			  auto e = *it2;
			  *it2 = *prev;
			  *prev = e;
			}
		}
	}
}

template<class RandomIt, class Comparador>
void bubblesort(RandomIt comeco, RandomIt fim, Comparador cmp) {
	for (RandomIt it = fim - 1; it != comeco ; it--) {
		for (RandomIt it2 = comeco; it2 != it; it2++) {
			RandomIt next = it2 + 1;
			if (!cmp(*it2, *next)) {
			  auto e = *it2;
			  *it2 = *next;
			  *next = e;
			}
		}
	}
}


int main() {
	std::vector<int> v = {3, 3, 2, 1};
	insertionsort(v.begin(), v.end(), [](int a, int b) { return a < b; });
	my_for_each(v.begin(), v.end(), [](int a) { std::cout << a << std::endl; });

	std::vector<int> v2 = {3, 3, 2, 1};
	bubblesort(v2.begin(), v2.end(), [](int a, int b) { return a < b; });
	my_for_each(v2.begin(), v2.end(), [](int a) { std::cout << a << std::endl; });
	return 0;
}