#include <iostream>
#include <vector>
#include <string>

class Populated_locality {
private:
	std::string name;
	int population;
public:
	Populated_locality(){}

	Populated_locality(std::string name, int population) {
		this->name = name;
		this->population = population;
	}

	std::string get_name() {
		return name;
	}

	int get_population() {
		return population;
	}
};

class Locality_array {
private:
	std::vector<Populated_locality> p_l_array;
	int length;
public:
	Locality_array() {
		p_l_array = {};
		length = 0;
	}

	void add(Populated_locality obj) {
		p_l_array.push_back(obj);
		length++;
	}

	void print() {
		int i = 1;
		for (Populated_locality n : p_l_array) {
			std::cout << i << ' ';
			std::cout << n.get_name() << '\n';
			std::cout << n.get_population() << '\n';
			i++;
		}
	}
	void easy_selection_sort() {

		int min;
		Populated_locality tmp;

		for (int i = 0; i < length - 1; i++) {
			min = i;
			for (int j = i + 1; j < length; j++) {
				if (p_l_array[j].get_name() < p_l_array[i].get_name())
					min = j;
			}
			tmp = p_l_array[i];
			p_l_array[i] = p_l_array[min];
			p_l_array[min] = tmp;
		}
	}
	void quick_sort(int begin, int end) {

		int l = begin, r = end;
		std::string piv = p_l_array[(l + r) / 2].get_name();

		do {

			while (p_l_array[l].get_name() < piv)
				l++;
			while (p_l_array[r].get_name() > piv)
				r--;
			if (l <= r)
				std::swap(p_l_array[l++], p_l_array[r--]);



		} while (l <= r);
		if (begin < r) quick_sort(begin, r);
		if (end > l) quick_sort(l, end);

	}

	std::vector<Populated_locality> get_p_l_array() {
		return p_l_array;
	}
	int get_length() {
		return length;
	}
};

void main_menu(char *ch) {
	setlocale(LC_ALL, "Russian");
	std::cout << "1  (P)rint - Вывод коллекциина экран." << '\n';
	std::cout << "2  (A)dd - Вставка нового объекта." << '\n';
	std::cout << "3  (I)nsert - Вставка нового объекта по указанному индексу." << '\n';
	std::cout << "4  (D)elete - Удаление объекта по указанному индексу." << '\n';
	std::cout << "5  (G)et - Получение объекта поуказанному индексу." << '\n';
	std::cout << "6  (S)ize - Получение количества объектов в коллекции." << '\n';
	std::cout << "7  (F)ind - Простой поиск объекта по полю «Название населенного пункта»." << '\n';
	std::cout << "8  (B)inary find - Бинарный поиск объекта по полю «Название населенного пункта»." << '\n';

	std::cout << "9  (Q)uick Sort - Сортировка коллекции \"Быстрой сортировкой\"." << '\n';
	std::cout << "10  Simpl(e) Sort - Сортировка коллекции \"Сортировка простым выбором\"." << '\n';
	std::cin >> *ch;

}
void add_in_collection(Locality_array *data_base) {
	std::string name;
	int population;
	std::cout << "Введите название населенного пункта." << '\n';
	std::cin >> name;
	std::cout << "Введите количество жителей населенного пункта." << '\n';
	std::cin >> population;
	Populated_locality obj(name, population);
	data_base->add(obj);

}


int main() {
	Locality_array data_base;
	char ch = 0;
	while (ch != 'x') {
		main_menu(&ch);
		switch (ch) {
		case 'p':
			data_base.print();
			break;
		case 'a':
			add_in_collection(&data_base);
			break;
		case 's':
			std::cout << data_base.get_length() << '\n';
			break;
		case 'q':
			data_base.quick_sort(0, data_base.get_length() - 1);
			break;
		case 'e':
			data_base.easy_selection_sort();
			break;
		}

	}

	data_base.print();

	std::cout << '\n';

	data_base.print();
	int pause;
	std::cin >> pause;
	getchar();
}