Сортировка
Это понятие впервые встречается на программе «Инженерия и системный подход к решению задач» — примерно 11-12 лет (5-6 класс).
Расстановка списка по порядку: числа — по возрастанию, слова — по алфавиту. В упорядоченном списке нужное находится гораздо быстрее.
Книги на полке по алфавиту: нужную находишь сразу, а в случайной куче перебираешь всё подряд.
Разложить 10 карточек с числами по возрастанию и проговорить, как выбираешь, куда положить следующую карточку.
Перестановка элементов списка по ключу — числу, дате, алфавиту — по возрастанию или убыванию. Выполняет её алгоритм: компьютер много раз сравнивает пары элементов и меняет их местами. В таблице сортируют по столбцу-ключу, и строки переставляются целиком.
В электронной таблице отсортировать список класса по росту и по имени; объяснить, почему при сортировке строки переставляются целиком.
Задача упорядочивания n элементов сравнениями. Простые алгоритмы (пузырёк, вставки) делают порядка n² сравнений, быстрые (слияние, quicksort) — n·log n: на миллионе элементов разница в десятки тысяч раз. Важное свойство — устойчивость: сохраняется ли взаимный порядок равных элементов. Сортировка — плата за последующий быстрый поиск.
Отсортировать 16 карточек пузырьком и слиянием, посчитать сравнения в обоих случаях и сравнить результат с оценками n² и n·log n.
Частое заблуждение
«Сортировка — это разложить по кучкам, как мусор по бакам». В информатике сортировка — выстроить все элементы в один ряд по порядку признака; раскладывание по группам — другая задача.