Сортировка, функции и рекурсия в двух языках

На собеседовании не требуется заново писать быструю сортировку, если задача лишь нуждается в порядке. Важно точно задать правило сравнения, понимать, меняется ли исходный контейнер, и уметь сформулировать базовый случай рекурсивной функции.

Как упорядочить записи по двум полям

Даны пары (идентификатор, приоритет). Нужно упорядочить их сначала по возрастанию приоритета, а при равенстве — по идентификатору. Отдельно разберём, как читать естественную рекуррентную формулировку, не подменяя ею обычный линейный проход.

Почему собственная сортировка здесь лишняя

Можно написать собственную сортировку: многократно искать минимальную оставшуюся пару и переносить её в ответ. Это O(n²) сравнений и лишний источник ошибок в индексах. Можно также сравнивать только приоритет и забыть правило равенства — тогда результат не соответствует полному контракту.

Где смешиваются порядок и перестановка

Задаче не нужен новый алгоритм сортировки. Нужна корректная функция порядка. Самодельные циклы смешивают две ответственности: эффективную перестановку элементов и предметное правило «какая пара раньше».

Передаём библиотеке точное правило

Стандартная сортировка уже решает перестановочную часть за O(n log n). В C++ ей передают компаратор comesBefore(left, right), который отвечает строгим булевым значением. В Python функция key превращает элемент в сравнимый ключ; кортежи сравниваются лексикографически.

Рекурсию лучше читать как обещание функции для меньшего входа. Например, sumTo(3) означает 3 + sumTo(2), затем 2 + sumTo(1), а sumTo(0) = 0 останавливает цепочку. Здесь состояние — оставшееся n, базовый случай — ноль, уменьшение — n - 1. Для простого длинного прохода всё равно выбирают цикл: модель рекурсии полезна, но стек вызовов не бесплатен.

Сортируем по одному явному правилу

1. Определить единый ключ пары (second, first), то есть (приоритет, идентификатор).
2. Отсортировать стандартной библиотекой по этому ключу.
3. Отдельно решить, должен ли исходный контейнер измениться или нужен новый.
4. Для рекурсивной задачи до кода назвать смысл состояния, базовый случай и строгое уменьшение входа.

Один порядок для C++ и Python

C++17

#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>

using namespace std;

using Item = pair<int, int>;  // identifier, priority

bool comesBefore(const Item& left, const Item& right) {
    return pair{left.second, left.first} < pair{right.second, right.first};
}

int main() {
    vector<Item> values{{2, 1}, {1, 1}, {0, 3}};
    sort(values.begin(), values.end(), comesBefore);

    assert((values == vector<Item>{{1, 1}, {2, 1}, {0, 3}}));
    assert(!comesBefore(values[0], values[0]));
}

Python 3

Item = tuple[int, int]  # identifier, priority


def order_key(item: Item) -> tuple[int, int]:
    identifier, priority = item
    return priority, identifier


values = [(2, 1), (1, 1), (0, 3)]
ordered = sorted(values, key=order_key)

assert ordered == [(1, 1), (2, 1), (0, 3)]
assert values == [(2, 1), (1, 1), (0, 3)]

Цена сортировки и копии

Сортировка занимает O(n log n) сравнений. В C++ std::sort меняет вектор и обычно использует O(log n) служебного стека; Python sorted создаёт новый список, стабилен и требует O(n) дополнительной памяти для результата и служебных данных. Рекурсивная цепочка глубины n отдельно потребовала бы O(n) стековых кадров, поэтому простой длинный проход лучше записать циклом.

Равные поля, пустой список и изменение входа

• Пустой и одноэлементный контейнер уже отсортированы.
• Полностью равные пары: строгий компаратор должен вернуть false в обе стороны.
• Равные приоритеты требуют сравнения идентификаторов.
• В Python sorted не меняет values, а list.sort() меняет его на месте.

Проверяем правило равенства и семантику копии

Проверь пустой и одноэлементный вход, пары с разными приоритетами, равные приоритеты и полностью равные пары. Отдельно проверь семантику изменения: после sorted исходный список Python должен остаться прежним; после std::sort вектор C++ изменён.

Когда порядок открывает структуру задачи

Сортировка полезна, когда после упорядочивания нужные кандидаты становятся соседями, появляется монотонность или требуется обработка событий по времени. Рекурсия естественна, когда задача сводится к такой же задаче меньшего размера и есть чёткий базовый случай.

Когда сортировка или рекурсия создают лишнюю цену

Не сортируй, если исходный порядок нужно сохранить, а копия слишком дорога, или если достаточно линейного поиска одного экстремума. Не используй глубокую рекурсию для простого длинного прохода в Python: цикл безопаснее для стека.

Почему компаратор обязан быть строгим

Вопрос. Почему компаратор C++ не должен возвращать true для двух равных элементов?

Ответ. std::sort требует строгого порядка. Если одновременно a < a, контракт нарушен, и поведение сортировки не определяет корректный результат.

Чем ключ отличается от компаратора

Вопрос. Чем key в Python отличается от компаратора C++?

Ответ. key один раз описывает сравнимое представление каждого элемента, например (priority, id). Компаратор получает два элемента и отвечает, должен ли левый стоять раньше правого.

Добавляем имя и обратный приоритет

Добавь третье поле name и упорядочь записи по убыванию приоритета, затем по возрастанию имени. Подсказка: в Python ключ может быть (-priority, name), а в C++ компаратор должен явно обработать неравные приоритеты и затем сравнить имена.

Самостоятельная задача о расписании докладов

Задача 1

Даны доклады как тройки (start, end, title). Верните новую последовательность, упорядоченную сначала по окончанию, затем по началу, затем по названию; исходную последовательность изменять нельзя. Реализуйте одинаковый контракт на C++17 и Python и перечислите тесты для равных полей.

Явный порядок делает код переносимым

Передавай стандартной сортировке одно точное правило порядка, различай изменение и копирование контейнера, а в рекурсии всегда называй состояние, базовый случай и уменьшение задачи.