Сравнение алгоритмов сортировки на Python с Pygame-визуализацией

Когда объясняешь школьникам или студентам, как работает сортировка, графика говорит громче слов. Наверняка, в интернете полно обзоров и сравнительных анализов различных алгоритмов сортировки, но я не нашел ничего что объединяло бы самые популярные алгоритмы в одном сравнительном экстазе. Поэтому я написал визуализатор, который показывает в реальном времени, как разные алгоритмы сортируют один и тот же массив — одновременно.

Зачем нужен визуализатор

Когда мы говорим о «скорости сортировки», большинство представляет себе просто числа и асимптотику O(n log n).
Но если вы хоть раз увидите, как пузырьковая сортировка «ползёт» по массиву, а QuickSort разлетается молнией, — асимптотика станет куда понятнее.

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

Что делает программа

Программа строит окно Pygame, разбитое на несколько панелей (по одной на каждый алгоритм).
На каждой панели — набор прямоугольных столбиков, представляющих элементы массива.
Высота — значение, цвет — алгоритм.

• Визуализация 10 алгоритмов сортировки одновременно

• Пошаговая анимация — видно каждый обмен элементов

• Реальное сравнение скорости и динамики алгоритмов

• Управление в реальном времени (пауза, перезапуск, скорость)

• Полностью на чистом Python, без внешних зависимостей кроме pygame

Во время работы:

• Все алгоритмы запускаются на одной и той же случайной выборке чисел.

• Каждый шаг сортировки отрисовывается в реальном времени.

• Можно ставить на паузу, перезапускать с новой выборкой, или наблюдать завершение каждого метода.

Поддерживаемые алгоритмы

Визуализатор реализует все классические алгоритмы сортировки на 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