Сортировки на Python: как решать + 11 задач с проверкой

Сортировка — это упорядочивание элементов (чисел, строк, пар) по возрастанию или убыванию. В олимпиадных задачах она встречается в рейтингах и таблицах мест, поиске «k‑го» элемента, группировке одинаковых значений, а ещё в задачах про ближайшие объекты: после сортировки ответы часто находятся среди соседей.

Как распознать, что нужна сортировка:

• в условии есть слова «отсортировать», «место в таблице», «k‑й по величине», «топ‑m», «медиана»;
• нужно быстро сравнивать много элементов между собой (например, найти минимальную разницу, «опасную пару», совпадения/почти совпадения);
• важны дубликаты: одинаковые значения должны стоять рядом и учитывать «занятые места» подряд.

Суть приёма: сначала упорядочиваем массив по нужному ключу (по убыванию очков, по коду, по координате дома). После этого многие вопросы решаются одним проходом: взять элемент на позиции k, посчитать серии равных, проверить только соседние пары. Это ускоряет решение, потому что вместо множества сравнений «каждый с каждым» мы тратим время на одну сортировку и линейный просмотр.

С чего начать учиться:

• уверенно пользоваться встроенной сортировкой и компаратором (сортировка по убыванию, по паре: сначала одно поле, потом другое);
• помнить про индексацию: k‑е место — это элемент с индексом k‑1 в отсортированном массиве;
• тренировать приёмы «после сортировки»: пройти по массиву и обработать соседей, серии одинаковых, минимальные разницы;
• различать полную сортировку и поиск k‑го элемента (когда нужен только один ответ, а не весь порядок).

Ниже — задачи с автопроверкой и разбором подхода: начнём с простых рейтингов и постепенно перейдём к «парам» и «почти одинаковым» данным.