"А где тут сортировка

"А где тут сортировка?"

Недавно разбирали с учеником одну задачу №26 из резерва ЕГЭ-2023 (прочитать условие).

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

Решение вроде бы вообще не похоже на классическую сортировку:

🟡 в момент входа делаем +1

🟡 в момент выхода делаем -1

🟡 дальше проходим по минутам и считаем накопленное количество людей

И тут ученик задаёт очень логичный вопрос:

"Вы же всегда говорите, что №26 = сортировка. А где здесь сортировка? Мы же вообще не используем ни sort, ни sorted".

И вот здесь начинается самое интересное. Сортировка тут есть. Просто она не выглядит как привычное:

a.sort()

или

sorted(a)

По сути, здесь работает та же идея, на которой построен counting sort.

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

Например, если нам даны минуты от 0 до 1440, то это идеальная ситуация: диапазон небольшой, фиксированный, удобный.

Мы не сортируем события явно. Мы раскладываем изменения сразу по "правильным местам" - по индексам минут.

А потом просто идём по списку слева направо. То есть порядок уже зашит в индексах.

Именно поэтому такая задача всё равно относится к логике сортировки данных, хотя в коде нет ни sort, ни sorted.

Это, кстати, важный момент для преподавания №26. Ученики часто воспринимают сортировку слишком буквально: "Если нет .sort(), значит сортировки нет".

Но в реальных задачах ЕГЭ сортировка может быть не только явной, но и скрытой - через индексы. И если ученик это не чувствует, он начинает теряться в современных №26.

Поэтому я собрал отдельный PDF по сортировке списков для задания №26. Внутри разобрал:

➖ метод sort

➖ функцию sorted

➖ параметр reverse

➖ параметр key

➖ сортировку двумерных списков

➖ сортировку по нескольким критериям

➖ как писать свои функции для key

➖ какие ошибки чаще всего возникают у учеников

Это не просто "как отсортировать список в Python", а именно методичка под №26 ЕГЭ по информатике.

Коллеги, кому нужен PDF - пишите мне в личку @max_egeinf слово "сортировка", я скину бесплатно.

#информатика

#задание26