Визуализация быстрой сортировки с SFML и C++20
В этой статье мы создадим интерактивную визуализацию алгоритма быстрой сортировки (QuickSort) с использованием библиотеки SFML и современных возможностей C++20. Этот проект поможет вам лучше понять, как работает один из самых популярных алгоритмов сортировки, и покажет, как можно комбинировать графику и алгоритмы для создания образовательных инструментов.
Зачем визуализировать алгоритмы?
Алгоритмы сортировки, такие как QuickSort, могут быть сложными для понимания, особенно для новичков.
Визуализация помогает:
Увидеть, как данные перемещаются и сравниваются на каждом шаге.
Понять концепции разбиения и рекурсии.
Сделать обучение более интерактивным и увлекательным.
Если вы хотите не только изучить алгоритмы, но и создать что-то наглядное и красивое, этот проект для вас!
Что нам понадобится?
SFML: Библиотека для работы с графикой, событиями и окнами. Скачать и установить.
Компилятор с поддержкой C++20: Например, GCC или Clang.
Базовые знания C++: Работа с векторами, лямбда-функциями и рекурсией.
Описание проекта
Цель
Создать программу, которая:
Генерирует случайный массив чисел.
Визуализирует его как набор столбцов.
Анимирует процесс сортировки с помощью QuickSort.
Особенности
Использование std: ranges из C++20 для удобной работы с диапазонами.
Рекурсивная реализация QuickSort с визуализацией на каждом шаге.
Простая, но эффективная анимация с задержкой для наглядности.
Код проекта
Подготовка
Установите SFML и настройте ваш проект (например, через CMake или вручную подключите библиотеки).
Убедитесь, что ваш компилятор поддерживает C++20 (флаг -std=c++20).
#include
#include
#include
#include
#include
#include
int main() {
// Настройки окна
sf::RenderWindow window(sf::VideoMode(1280, 720), "QuickSort Visualization");
window.setFramerateLimit(60);
// Генерация случайного массива чисел
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(10, 700);
std::vector arr(150);
for (auto& x : arr) x = dis(gen);
// Функция быстрой сортировки с визуализацией процесса
auto quickSort = [&](auto& range, int low, int high, auto& recur) mutable {
if (low >= high) return; // Базовый случай рекурсии
int pivot = range[high]; // Выбираем опорный элемент (последний в диапазоне)
int i = low - 1;
// Разделение элементов: меньшие идут влево, большие вправо
for (int j = low; j < high; ++j) {
if (range[j] <= pivot) {
++i;
std::swap(range[i], range[j]);
}
}
std::swap(range[i + 1], range[high]); // Устанавливаем опорный элемент на своё место
int pi = i + 1; // Индекс опорного элемента
// Рекурсивная сортировка левой и правой частей
recur(range, low, pi - 1, recur);
recur(range, pi + 1, high, recur);
// Визуализация текущего состояния массива
window.clear();
float barWidth = static_cast(window.getSize().x) / arr.size();
for (int k = 0; k < arr.size(); ++k) {
sf::RectangleShape bar(sf::Vector2f(barWidth - 1, arr[k]));
bar.setPosition(k * barWidth, window.getSize().y - arr[k]);
bar.setFillColor(sf::Color::White);
window.draw(bar);
}
window.display();
std::this_thread::sleep_for(std::chrono::milliseconds(50)); // Задержка для анимации
};
// Используем std::ranges для удобной работы с массивом
auto range = std::ranges::subrange(arr.begin(), arr.end());
bool sorting = true; // Флаг, чтобы сортировка выполнялась только один раз
// Основной цикл программы
while (window.isOpen()) {
sf::Event event;
while (window.pollEvent(event)) {
if (event.type == sf::Event::Closed) window.close(); // Закрытие окна
}
if (sorting) {
quickSort(range, 0, arr.size() - 1, quickSort); // Запуск сортировки
sorting = false; // Отключаем повторную сортировку
}
// Отрисовка финального состояния массива
window.clear();
float barWidth = static_cast(window.getSize().x) / arr.size();
for (int i = 0; i < arr.size(); ++i) {
sf::RectangleShape bar(sf::Vector2f(barWidth - 1, arr[i]));
bar.setPosition(i * barWidth, window.getSize().y - arr[i]);
bar.setFillColor(sf::Color::White);
window.draw(bar);
}
window.display();
}
return 0;
} Пояснения к коду
Генерация массива: Создаем вектор из 150 случайных чисел от 10 до 700 с помощью std: random_device и std: mt19937.
QuickSort: Реализован как лямбда-функция с рекурсией. На каждом шаге разбиения массива мы визуализируем текущее состояние.
Визуализация: Каждый элемент массива отображается как прямоугольник (sf: RectangleShape), высота которого пропорциональна значению элемента.
Анимация: Задержка в 50 миллисекунд (std: this_thread: sleep_for) между шагами сортировки создает эффект плавной анимации.
Как это работает?
При запуске программы генерируется случайный массив, который отображается как набор столбцов в окне SFML.
Алгоритм QuickSort начинает сортировку, и на каждом шаге разбиения массива окно обновляется, показывая текущее состояние.
После завершения сортировки вы видите отсортированный массив.
Попробуйте запустить код и понаблюдать за процессом — это действительно увлекательно!
Расширяемость проекта
Хотите сделать проект еще интереснее? Вот несколько идей:
Добавьте другие алгоритмы сортировки (например, пузырьковую или сортировку слиянием) и сравните их визуально.
Включите интерактивные элементы: кнопки для запуска сортировки или изменения скорости анимации.
Экспериментируйте с цветами: выделяйте опорный элемент (pivot) другим цветом для наглядности.
Заключение
Визуализация алгоритмов — это мощный инструмент для обучения и отладки. С помощью SFML и C++20 вы можете создавать не только полезные, но и красивые образовательные проекты. Этот пример демонстрирует, как комбинировать графику, алгоритмы и современные возможности языка для создания интерактивных приложений.
Попробуйте улучшить этот проект: добавьте звуковые эффекты, измените стиль визуализации или реализуйте другой алгоритм. Делитесь своими идеями в комментариях — мне будет интересно узнать, что вы придумали!
Телеграмм канал — Программирование игр С++
Habrahabr.ru прочитано 18143 раза
