Сортировки
Сортировка как инструмент: std::sort, компараторы, сортировка структур.
Сортировка — самый используемый алгоритм в олимпиадах, но не как самоцель, а как инструмент: после сортировки задача часто упрощается радикально. Ближайшая пара чисел? Отсортируйте — и она окажется среди соседей. Жадный выбор? Почти всегда начинается со «отсортируем по...».
Писать сортировку руками не нужно: std::sort работает за O(n log n). Нужно уметь ей управлять — задавать компаратор, то есть правило сравнения.
Сортировка по возрастанию и по убыванию. Введите: 5, затем 3 1 4 1 5
Компаратор — функция «должен ли x стоять раньше y». Лямбда [](int x, int y) { return x > y; } даёт убывание.
Настоящая сила — сортировка структур по любому полю. Отсортируем учеников по баллам: правило сравнения читается прямо из кода.
Введите: 3, затем строки вида «имя балл»: Azat 90, Aigul 98, Bek 85
Python
То же самое на Python: параметр key. Тот же ввод
Полезно знать: std::stable_sort сохраняет порядок равных элементов (важно при сортировке «по баллам, а при равенстве — по имени» в два прохода).
Задание: отсортируйте список слов сначала по длине, а при равной длине — по алфавиту (подсказка: компаратор с двумя условиями).
Отметьте урок пройденным и переходите к методу двух указателей.