Когда объясняешь школьникам или студентам, как работает сортировка, графика говорит громче слов. Наверняка, в интернете полно обзоров и сравнительных анализов различных алгоритмов сортировки, но я не нашел ничего что объединяло бы самые популярные алгоритмы в одном сравнительном экстазе. Поэтому я написал визуализатор, который показывает в реальном времени, как разные алгоритмы сортируют один и тот же массив — одновременно.
Зачем нужен визуализатор
Когда мы говорим о «скорости сортировки», большинство представляет себе просто числа и асимптотику O(n log n).
Но если вы хоть раз увидите, как пузырьковая сортировка «ползёт» по массиву, а QuickSort разлетается молнией, — асимптотика станет куда понятнее.
Так появилась идея: сделать наглядную, динамическую визуализацию, где все алгоритмы сортируют одни и те же данные параллельно.
Что делает программа
Программа строит окно Pygame, разбитое на несколько панелей (по одной на каждый алгоритм).
На каждой панели — набор прямоугольных столбиков, представляющих элементы массива.
Высота — значение, цвет — алгоритм.
Визуализация 10 алгоритмов сортировки одновременно
Пошаговая анимация — видно каждый обмен элементов
Реальное сравнение скорости и динамики алгоритмов
Управление в реальном времени (пауза, перезапуск, скорость)
Полностью на чистом Python, без внешних зависимостей кроме pygame
Во время работы:
Все алгоритмы запускаются на одной и той же случайной выборке чисел.
Каждый шаг сортировки отрисовывается в реальном времени.
Можно ставить на паузу, перезапускать с новой выборкой, или наблюдать завершение каждого метода.
Поддерживаемые алгоритмы
Визуализатор реализует все классические алгоритмы сортировки на Python (через генераторы):
Категория | Алгоритмы |
|---|---|
Простые | Bubble, Selection, Insertion |
Быстрые | Quick, Merge, Heap |
Гибридные | Shell, Comb, Gnome |
Реальные | TimSort (как в Python) |
Каждый алгоритм реализован как генератор, который yield-ит текущее состояние массива.
Это позволяет синхронно отрисовывать прогресс и наблюдать шаг за шагом.
Чуть более подробно про каждый из алгоритмов
1. Bubble Sort (пузырьковая сортировка)
Тип: простая, учебная
Сложность: O(n²)
Принцип: последовательно «всплывает» максимальный элемент в конец массива, сравнивая соседние пары.
Особенности: крайне медленная, но идеальна для демонстрации.
2. Selection Sort (сортировка выбором)
Тип: простая, сравнительная
Сложность: O(n²)
Принцип: находит минимум из оставшейся части и ставит его на текущее место.
Особенности: делает минимум обменов, но остаётся медленной.
3. Insertion Sort (сортировка вставками)
Тип: простая, адаптивная
Сложность: O(n²) в худшем, O(n) в лучшем
Принцип: вставляет каждый элемент на своё место в уже отсортированной части.
Особенности: быстра для почти отсортированных массивов.
4. Merge Sort (сортировка слиянием)
Тип: рекурсивная, стабильная
Сложность: O(n log n)
Принцип: делит массив пополам, сортирует рекурсивно, потом сливает.
Особенности: стабильная, требует доп. памяти (O(n)).
5. Quick Sort (быстрая сортировка)
Тип: рекурсивная, сравнительная
Сложность: O(n log n) в среднем, O(n²) в худшем
Принцип: выбирает опорный элемент, разделяет массив на меньшие/большие.
Особенности: самая быстрая в среднем, не стабильная.
6. Heap Sort (пирамидальная сортировка)
Тип: сравнительная, не рекурсивная
Сложность: O(n log n)
Принцип: строит двоичную кучу и последовательно извлекает максимум.
Особенности: не требует доп. памяти, всегда предсказуемая скорость.
7. Shell Sort (сортировка Шелла)
Тип: улучшение вставок
Сложность: от O(n log² n) до O(n^(3/2)), в зависимости от шага
Принцип: сортирует элементы через определённые промежутки (gap), постепенно уменьшая gap.
Особенности: часто используется для больших почти-отсортированных массивов.
8. Comb Sort (расчёстка)
Тип: улучшение пузырьковой
Сложность: O(n²) (на практике быстрее Bubble)
Принцип: похожа на пузырьковую, но сравнивает элементы через уменьшающийся «зазор».
Особенности: быстрее пузырьковой, простой код.
9. Gnome Sort (садовая сортировка)
Тип: экзотическая вариация вставок
Сложность: O(n²)
Принцип: похожа на сортировку вставками, но с интуитивным «шагом назад» при обмене.
Особенности: визуально интересная, «шагает» по массиву, как гном с цветами 🌼
10. TimSort
Тип: гибрид Merge + Insertion
Сложность: O(n log n)
Принцип: делит массив на небольшие блоки (runs), сортирует вставками и сливает.
Особенности: используется в Python (list.sort, sorted) и Java — один из лучших реальных алгоритмов сортировки.
Техническая реализация
Основная идея
Главная структура — это словарь генераторов:
generators = {name: func(list(arr)) for name, func in ALGORITHMS.items()} arrays = {name: list(arr) for name in ALGORITHMS.keys()}
Каждый кадр цикла main() вызывает:
state = next(gen) arrays[name] = state
и сразу же перерисовывает панели.
Интерфейс
ESC — выход
SPACE — пауза / продолжение
R — перезапустить с новой случайной выборкой
Экран делится на сетку cols × rows, каждая ячейка отображает один алгоритм.
Пример при 10 алгоритмах — сетка 5×2.
Пример визуализации
Pygame обеспечивает стабильный FPS (60 кадров/с) и простое управление окнами.
Все сортировки написаны на чистом Python — без NumPy.
Генераторы позволяют элегантно «пошагово» наблюдать процесс.
Для каждого алгоритма сохраняется отдельная копия массива, чтобы стартовые условия были одинаковыми.
Результат и выводы
Разумеется, результат абсолютно предсказуемый, но мною преследовалась цель повысить наглядность при сравнении скорости сортировки раличных алгоритмов:
Пузырьковая сортировка — самая медленная (как и ожидалось).
QuickSort и HeapSort лидируют.
MergeSort стабильно быстра, но требует больше движений.
TimSort показывает плавное, оптимизированное поведение, почти как в реальной сортировке Python.
Можно было бы добавить еще алгоритмы RadixSort, CountingSort, BucketSort, но, как по мне, они слишком специфичны по отношению к сортируемым данным.
Этот проект — отличный пример, как можно совместить:
классическую алгоритмическую теорию,
простую визуализацию на Python,
и интерактивное обучение.
Полезно для школьников, студентов и просто тех, кто любит видеть, как алгоритмы оживают, визуалов и просто фанатов инфографики 🙂
Ну и, как полагается, исходный код доступен на GitHub
На вики можно почитать про каждый алгоритм более подробно
Источник: habr.com
