Сортировки в C++: пузырьком, выбором и перемешиванием — тест

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

Какие темы охватывает набор

Сортировка пузырьком: сравнение соседей, «всплывание» наибольшего элемента, досрочная остановка, если за проход не было обменов. Сортировка выбором: поиск минимума неупорядоченной части и один обмен за проход. Сортировка перемешиванием (шейкерная): проходы в обе стороны. Обмен через временную переменную и функция swap. Число сравнений и обменов, инверсии, устойчивость сортировки. Стандартная функция std::sort, сортировка по убыванию, оценка времени для больших массивов.

Как устроена работа

Пятнадцать заданий: выбор ответа, соответствие алгоритма и его характерного свойства, порядок шагов сортировки выбором, вставка недостающих частей обмена и задания на трассировку — состояние массива после прохода, число сравнений, число обменов пузырька по инверсиям и результат std::sort.

Разбор и подготовка

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

Кому пригодится

Учителю — для контроля после темы сортировок, в том числе как устная разминка по трассировке. Ученику — как подготовка к олимпиадам и к теме сложности алгоритмов.

Технические возможности

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