#include <iostream>
#include <vector>
#include <iterator>
#include <iterator>
#include <map>

using std::vector;

template<typename RandomIt>
void InsertionSort(RandomIt begin, RandomIt end) {
    for (auto it = begin + 1; it < end; ++it) {
        auto current_value = *it;
        auto prev_it = std::prev(it);
        while (prev_it >= begin && *prev_it > current_value) {
            *std::next(prev_it) = *prev_it;
            --prev_it;
        }
        *std::next(prev_it) = current_value;
    }
}

template<typename RandomIt>
void CountingSort(RandomIt begin, RandomIt end) {
    using ValueType = typename std::iterator_traits<RandomIt>::value_type;
    std::map<ValueType, std::size_t> counts;

    for (auto value = begin; value != end; ++value) {
        ++counts[*value];
    }

    for (auto &count: counts) {
        ValueType value = count.first;
        size_t size = count.second;
        std::fill_n(begin, size, value);
        std::advance(begin, size);
    }
}

struct person {
    std::string name;
    int age;
};

bool operator<(const person &lhs, const person &rhs) {
    return lhs.name < rhs.name;
}

bool operator>(const person &lhs, const person &rhs) {
    return lhs.name > rhs.name;
}

bool operator==(const person &lhs, const person &rhs) {
    return lhs.name == rhs.name;
}

void RunSortTestExample() {
    vector<int> vector1 = {1, 5, 7, 82, 3, 5, 7, 12};
    InsertionSort(vector1.begin(), vector1.end());
    for (auto x:vector1) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    int array[] = {1, 5, 72, 3, 42, 45, 2, 35, 6};
    InsertionSort(std::begin(array), std::end(array));
    for (auto x:array) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    vector<person> persons = {
            {
                    "ilya",
                    18,
            },
            {
                    "egor",
                    19,
            },
            {
                    "yana",
                    22,
            },
            {
                    "andrei",
                    20,
            }

    };
    InsertionSort(persons.begin(), persons.end());
    for (const auto&[name, age]:persons) {
        std::cout << name << " " << age << std::endl;
    }
}

void RunCountingSortTestExample() {
    vector<int> vector1 = {1, 5, 7, 82, 3, 5, 7, 12};
    CountingSort(vector1.begin(), vector1.end());
    for (auto x:vector1) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    int array[] = {1, 5, 72, 3, 42, 45, 2, 35, 6};
    CountingSort(std::begin(array), std::end(array));
    for (auto x:array) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    vector<person> persons = {
            {
                    "ilya",
                    18,
            },
            {
                    "egor",
                    19,
            },
            {
                    "yana",
                    22,
            },
            {
                    "andrei",
                    20,
            }

    };
    CountingSort(persons.begin(), persons.end());
    for (const auto&[name, age]:persons) {
        std::cout << name << " " << age << std::endl;
    }
}

int main() {
    RunSortTestExample();
    RunCountingSortTestExample();
    return 0;
}