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

using std::vector;

template<typename RandomIt>
void SelectionSort(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;
    }
}

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};
    SelectionSort(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};
    SelectionSort(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,
            }

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

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