Пузырьковая, вставками, слиянием, быстрая и пирамидальная на одной перестановке — пять рядов столбиков шагают синхронно.
О модели
Пять сравнительных сортировок работают на одной и той же перестановке чисел 1…n: пузырьковая (обмен соседей), вставками (сдвиг ключа назад), слияние снизу вверх (проходы удваивающейся ширины), быстрая с разбиением Ломуто и явным стеком диапазонов, пирамидальная (построение макс-кучи и просеивание при извлечении). Один общий микрошаг двигает все пять сразу: видно разные картины перестановок, а не гонку по времени процессора — у методов разное число шагов. Столбики окрашены по исходному индексу; подсветка — текущее сравнение или обмен. Это учебная анимация сравнений и обменов, не замер реальной сложности на конкретной машине.
Для кого: Вводный курс информатики: сравнение семейств O(n²) и O(n log n) на одной перестановке.
Ключевые понятия
пузырьковая сортировка
сортировка вставками
сортировка слиянием
быстрая сортировка
пирамидальная сортировка
разбиение Ломуто
двоичная куча
устойчивость сортировки
Как это работает
Одна перестановка 1…n, пять сортировок. Каждый микрошаг — сравнение или обмен — выполняется во всех рядах одновременно, поэтому видно, как по-разному переставляется массив у пузырька, вставок, слияния снизу вверх, быстрой (Ломуто) и пирамиды, а не только кто быстрее по часам.
Часто задаваемые вопросы
Почему ряды заканчиваются в разное время?
На одном входе разным алгоритмам нужно разное число сравнений и обменов. Общий шаг всё равно один на все пять: уже отсортированные ряды стоят, пока догоняют более «длинные» по числу операций.
Устойчива ли здесь сортировка слиянием?
При равных ключах в слиянии берут элемент из левой половины (условие ≤) — обычная устойчивая реализация. Остальные показанные методы устойчивость в общем случае не гарантируют.
Почему быстрая сортировка кажется «шумнее» пирамидальной?
Разбиение Ломуто сканирует подмассив и делает много обменов вокруг опорного элемента; в пирамидальной основная работа — просеивания вдоль пути в дереве. Порядок O(n log n) в типичном случае у обоих, но константы и картина движения разные.