Визуализация быстрой сортировки с 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 <SFML/Graphics.hpp>
#include <vector>
#include <ranges>
#include <random>
#include <chrono>
#include <thread>
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<int> 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<float>(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<float>(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 вы можете создавать не только полезные, но и красивые образовательные проекты. Этот пример демонстрирует, как комбинировать графику, алгоритмы и современные возможности языка для создания интерактивных приложений.
Попробуйте улучшить этот проект: добавьте звуковые эффекты, измените стиль визуализации или реализуйте другой алгоритм. Делитесь своими идеями в комментариях — мне будет интересно узнать, что вы придумали!