task06_stable_sort

Задача 6. Сортировки C++23

Условие

Напишите функцию void stable_sort(int* arr, int n, int (*comparator)(int, int)) стабильной сортировки, принимающую на вход указатель на массив целых чисел arr длины n и компаратор для сравнения двух элементов массива comparator.

Идея решения

Используем сортировку вставками — она устойчивая по своей природе: при равенстве ключей элементы не меняют порядок. Компаратор возвращает > 0, если первый элемент должен идти после второго; при <= 0 порядок сохраняется.

Ввод

• Число n — длина массива.
• n строк с целыми числами — элементы массива.
• Число от 1 до 4 — тип компаратора:
  1. по возрастанию значений;
  2. по убыванию значений;
  3. по длине числа (при равной длине — по порядку в исходном массиве);
  4. по чётности: сначала чётные, потом нечётные (при одинаковой чётности — по порядку в исходном массиве).

Вывод

Элементы массива после сортировки, разделённые пробелами.

Пример 1

Ввод:

5
1
3
6
2
7
4

Вывод:

6 2 1 3 7

Пример 2

Ввод:

6
11
22
3
77
111
3
3

Вывод:

3 3 11 22 77 111

Как запустить

g++ -std=c++23 -O2 solution.cpp -o solution
./solution

Программа ждёт ввод с клавиатуры. Введи числа по одному, каждое с новой строки.

Ограничения

• Время: 1 сек
• Память: 64 МБ