Sorting algorithm visualizer in C++ and SDL2 Improved

Question

Original post: Sorting algorithm visualizer in C++ and SDL2
I followed the advice you gave me and improved my code. I also added two more sorting algorithms. I'm mainly looking for code readability advice (Built on Windows with cmake and ninja)

Demonstration

props to @Zeta for the demonstration

main.cpp

#include "Engine.h" #undef main int main() { try { // If the max number is higher than the window width it draws nothing other than a black screen :^) // Default draw method is line // Default sorting algorithm is bubble sort SortVis::Engine visualization( { 1024, 768 }, 1024, SortVis::Engine::SortAlgorithm::insertionSort, SortVis::Engine::DrawMethod::point ); visualization.run(); } catch (std::runtime_error& error) { std::cerr << error.what() << "\n"; } } 

Engine.h

#ifndef ENGINE_H #define ENGINE_H #include "Coord.h" #include <SDL.h> #include <vector> #include <iostream> namespace SortVis { class Engine { public: enum class DrawMethod { line, point }; enum class SortAlgorithm { selectionSort, insertionSort, bubbleSort }; // Random number generation Engine() = delete; Engine(Coord windowSize, int maxNumber); Engine(Coord windowSize, int maxNumber, SortAlgorithm algorithm); Engine(Coord windowSize, int maxNumber, SortAlgorithm algorithm, DrawMethod method); Engine(Coord windowSize, int maxNumber, const char* windowTitle); Engine(Coord windowSize, int maxNumber, const char* windowTitle, SortAlgorithm algorithm); Engine(Coord windowSize, int maxNumber, const char* windowTitle, SortAlgorithm algorithm, DrawMethod method); // Load from file Engine(Coord windowSize, const char* pathToNumbersFile); Engine(Coord windowSize, const char* pathToNumbersFile, SortAlgorithm algorithm); Engine(Coord windowSize, const char* pathToNumbersFile, SortAlgorithm algorithm, DrawMethod method); Engine(Coord windowSize, const char* pathToNumbersFile, const char* windowTitle); Engine(Coord windowSize, const char* pathToNumbersFile, const char* windowTitle, SortAlgorithm algorithm); Engine(Coord windowSize, const char* pathToNumbersFile, const char* windowTitle, SortAlgorithm algorithm, DrawMethod method); ~Engine(); void run(); private: const Coord windowSize; const SortAlgorithm selectedSortAlgorithm = SortAlgorithm::bubbleSort; const DrawMethod selectedDrawMethod = DrawMethod::line; SDL_Window* window = nullptr; SDL_Renderer* renderer = nullptr; std::vector<int> numbers = { }; int columnWidth = 0; int maxValue = 0; bool running = true; void initWindow(Coord windowSize, const char* windowTitle); void initRenderer(); void calculateNumbers(); void loadFile(const char* pathToNumbersFile); void handleEvents(); void draw(); void drawSelection(); void drawColumns(); void drawPoints(); void step(); void stepBubbleSort(); void stepInsertionSort(); void stepSelectionSort(); std::vector<int> generateRandom(int maxNumber); }; } #endif // ENGINE_H 

Engine.cpp

#include "Engine.h" #include <filesystem> #include <fstream> #include <random> #include <utility> #include <algorithm> #include <numeric> #include <string> // --- CONSTRUCTORS --- (fml) SortVis::Engine::Engine(Coord windowSize, int maxNumber) : windowSize(windowSize), numbers(generateRandom(maxNumber)) { calculateNumbers(); if (SDL_InitSubSystem(SDL_INIT_VIDEO) < 0) { throw std::runtime_error("Could not initialize SDL"); } initWindow(windowSize, "Sort visualizer"); initRenderer(); } SortVis::Engine::Engine(Coord windowSize, int maxNumber, SortAlgorithm algorithm) : windowSize(windowSize), numbers(generateRandom(maxNumber)), selectedSortAlgorithm(algorithm) { calculateNumbers(); if (SDL_InitSubSystem(SDL_INIT_VIDEO) < 0) { throw std::runtime_error("Could not initialize SDL"); } initWindow(windowSize, "Sort visualizer"); initRenderer(); } SortVis::Engine::Engine(Coord windowSize, int maxNumber, SortAlgorithm algorithm, DrawMethod method) : windowSize(windowSize), numbers(generateRandom(maxNumber)), selectedSortAlgorithm(algorithm), selectedDrawMethod(method) { calculateNumbers(); if (SDL_InitSubSystem(SDL_INIT_VIDEO) < 0) { throw std::runtime_error("Could not initialize SDL"); } initWindow(windowSize, "Sort visualizer"); initRenderer(); } SortVis::Engine::Engine(Coord windowSize, int maxNumber, const char* windowTitle) : windowSize(windowSize), numbers(generateRandom(maxNumber)) { calculateNumbers(); if (SDL_InitSubSystem(SDL_INIT_VIDEO) < 0) { throw std::runtime_error("Could not initialize SDL"); } initWindow(windowSize, windowTitle); initRenderer(); } SortVis::Engine::Engine(Coord windowSize, int maxNumber, const char* windowTitle, SortAlgorithm algorithm) : windowSize(windowSize), numbers(generateRandom(maxNumber)), selectedSortAlgorithm(algorithm) { calculateNumbers(); if (SDL_InitSubSystem(SDL_INIT_VIDEO) < 0) { throw std::runtime_error("Could not initialize SDL"); } initWindow(windowSize, windowTitle); initRenderer(); } SortVis::Engine::Engine(Coord windowSize, int maxNumber, const char* windowTitle, SortAlgorithm algorithm, DrawMethod method) : windowSize(windowSize), numbers(generateRandom(maxNumber)), selectedSortAlgorithm(algorithm), selectedDrawMethod(method) { calculateNumbers(); if (SDL_InitSubSystem(SDL_INIT_VIDEO) < 0) { throw std::runtime_error("Could not initialize SDL"); } initWindow(windowSize, windowTitle); initRenderer(); } SortVis::Engine::Engine(Coord windowSize, const char* pathToNumbersFile) : windowSize(windowSize) { if (!std::filesystem::exists(pathToNumbersFile)) { throw std::runtime_error("That file does not exist. Make sure the path is correct."); } else { loadFile(pathToNumbersFile); } calculateNumbers(); if (SDL_InitSubSystem(SDL_INIT_VIDEO) < 0) { throw std::runtime_error("Could not initialize SDL"); } initWindow(windowSize, "Sort visualizer"); initRenderer(); } SortVis::Engine::Engine(Coord windowSize, const char* pathToNumbersFile, SortAlgorithm algorithm) : windowSize(windowSize), selectedSortAlgorithm(algorithm) { if (!std::filesystem::exists(pathToNumbersFile)) { throw std::runtime_error("That file does not exist. Make sure the path is correct."); } else { loadFile(pathToNumbersFile); } calculateNumbers(); if (SDL_InitSubSystem(SDL_INIT_VIDEO) < 0) { throw std::runtime_error("Could not initialize SDL"); } initWindow(windowSize, "Sort visualizer"); initRenderer(); } SortVis::Engine::Engine(Coord windowSize, const char* pathToNumbersFile, SortAlgorithm algorithm, DrawMethod method) : windowSize(windowSize), selectedSortAlgorithm(algorithm), selectedDrawMethod(method) { if (!std::filesystem::exists(pathToNumbersFile)) { throw std::runtime_error("That file does not exist. Make sure the path is correct."); } else { loadFile(pathToNumbersFile); } calculateNumbers(); if (SDL_InitSubSystem(SDL_INIT_VIDEO) < 0) { throw std::runtime_error("Could not initialize SDL"); } initWindow(windowSize, "Sort visualizer"); initRenderer(); } SortVis::Engine::Engine(Coord windowSize, const char* pathToNumbersFile, const char* windowTitle) : windowSize(windowSize) { if (!std::filesystem::exists(pathToNumbersFile)) { throw std::runtime_error("That file does not exist. Make sure the path is correct."); } else { loadFile(pathToNumbersFile); } calculateNumbers(); if (SDL_InitSubSystem(SDL_INIT_VIDEO) < 0) { throw std::runtime_error("Could not initialize SDL"); } initWindow(windowSize, windowTitle); initRenderer(); } SortVis::Engine::Engine(Coord windowSize, const char* pathToNumbersFile, const char* windowTitle, SortAlgorithm algorithm) : windowSize(windowSize), selectedSortAlgorithm(algorithm) { if (!std::filesystem::exists(pathToNumbersFile)) { throw std::runtime_error("That file does not exist. Make sure the path is correct."); } else { loadFile(pathToNumbersFile); } calculateNumbers(); if (SDL_InitSubSystem(SDL_INIT_VIDEO) < 0) { throw std::runtime_error("Could not initialize SDL"); } initWindow(windowSize, windowTitle); initRenderer(); } SortVis::Engine::Engine(Coord windowSize, const char* pathToNumbersFile, const char* windowTitle, SortAlgorithm algorithm, DrawMethod method) : windowSize(windowSize), selectedSortAlgorithm(algorithm), selectedDrawMethod(method) { if (!std::filesystem::exists(pathToNumbersFile)) { throw std::runtime_error("That file does not exist. Make sure the path is correct."); } else { loadFile(pathToNumbersFile); } calculateNumbers(); if (SDL_InitSubSystem(SDL_INIT_VIDEO) < 0) { throw std::runtime_error("Could not initialize SDL"); } initWindow(windowSize, windowTitle); initRenderer(); } // --- END OF CONSTRUCTORS --- SortVis::Engine::~Engine() { SDL_DestroyRenderer(renderer); SDL_DestroyWindow(window); SDL_Quit(); } void SortVis::Engine::run() { // Sets render draw color to black SDL_SetRenderDrawColor(renderer, 0, 0, 0, 255); while (running) { handleEvents(); if (!std::is_sorted(numbers.begin(), numbers.end())) { step(); } draw(); } } void SortVis::Engine::step() { switch (selectedSortAlgorithm) { case SortAlgorithm::bubbleSort: stepBubbleSort(); break; case SortAlgorithm::insertionSort: stepInsertionSort(); break; case SortAlgorithm::selectionSort: stepSelectionSort(); break; default: break; } } void SortVis::Engine::stepBubbleSort() { static int i = 0; static int size = numbers.size(); for (int j = 0; j < size - i - 1; ++j) { if (numbers[j] > numbers[j + 1]) { std::swap(numbers[j], numbers[j + 1]); } } ++i; } void SortVis::Engine::stepInsertionSort() { static int i = 1; for (int j = i; j > 0 && numbers[j - 1] > numbers[j]; --j) { std::swap(numbers[j - 1], numbers[j]); } ++i; } void SortVis::Engine::stepSelectionSort() { static int i = 0; std::swap(numbers[i], numbers[std::min_element(numbers.begin() + i, numbers.end()) - numbers.begin()]); ++i; } void SortVis::Engine::draw() { SDL_RenderClear(renderer); drawSelection(); SDL_RenderPresent(renderer); } void SortVis::Engine::drawSelection() { switch (selectedDrawMethod) { case DrawMethod::line: drawColumns(); break; case DrawMethod::point: drawPoints(); break; default: break; } } void SortVis::Engine::drawColumns() { SDL_SetRenderDrawColor(renderer, 255, 255, 255, 255); SDL_Rect column; for (int i = numbers.size(); i > 0; --i) { column.x = (i-1) * columnWidth; column.w = columnWidth; column.h = (numbers[i - 1] * windowSize.Y) / maxValue; column.y = windowSize.Y - column.h; SDL_RenderFillRect(renderer, &column); } SDL_SetRenderDrawColor(renderer, 0, 0, 0, 255); } void SortVis::Engine::drawPoints() { SDL_SetRenderDrawColor(renderer, 255, 255, 255, 255); // SDL_Point point; for (int i = numbers.size(); i > 0; --i) { // point.x = i - 1; // point.y = windowSize.Y - ((numbers[i - 1] * windowSize.Y) / maxValue); SDL_RenderDrawPoint(renderer, i - 1, windowSize.Y - ((numbers[i - 1] * windowSize.Y) / maxValue)); } SDL_SetRenderDrawColor(renderer, 0, 0, 0, 255); } void SortVis::Engine::handleEvents() { SDL_Event Event; while (SDL_PollEvent(&Event)) { switch (Event.type) { case SDL_QUIT: running = false; break; default: break; } } } std::vector<int> SortVis::Engine::generateRandom(int maxNumber) { std::mt19937 seed(std::random_device{}()); std::vector<int> num(maxNumber); std::iota(num.begin(), num.end(), 0); std::shuffle(num.begin(), num.end(), seed); std::cout << "Generated random number sequence.\n"; return num; } void SortVis::Engine::calculateNumbers() { columnWidth = windowSize.X / numbers.size(); maxValue = *std::max_element(numbers.begin(), numbers.end()); } void SortVis::Engine::loadFile(const char* pathToNumbersFile) { std::ifstream NumbersFile(pathToNumbersFile); if (NumbersFile.is_open()) { std::string Number; while (std::getline(NumbersFile, Number)) { numbers.push_back(std::stoi(Number)); } } else { throw std::runtime_error("Couldn't open numbers file."); } if (numbers.empty()) { throw std::runtime_error("Numbers file is empty."); } std::cout << "Loaded numbers file.\n"; } void SortVis::Engine::initWindow(Coord windowSize, const char* windowTitle) { window = SDL_CreateWindow( windowTitle, SDL_WINDOWPOS_UNDEFINED, SDL_WINDOWPOS_UNDEFINED, windowSize.X, windowSize.Y, SDL_WINDOW_SHOWN ); if (window == nullptr) { throw std::runtime_error("Could not initialize SDL window"); } } void SortVis::Engine::initRenderer() { renderer = SDL_CreateRenderer( window, -1, SDL_RENDERER_PRESENTVSYNC | SDL_RENDERER_ACCELERATED ); if (renderer == nullptr) { throw std::runtime_error("Could not initialize SDL renderer"); } } 

Coord.h

#ifndef COORD_H #define COORD_H namespace SortVis { struct Coord { int X; int Y; }; } #endif // COORD_H 

Answer 1

The program is definitely improved from the earlier version. Nice job! Here are some things that may help you improve it further.

Don't Repeat Yourself (DRY)

There are eleven repetitions of the constructor, which seems a bit excessive to me, especially because the code is nearly identical. I would reduce those to exactly one:

Engine( Coord windowSize, std::vector<int>&& numbers, SortAlgorithm algorithm = SortAlgorithm::bubbleSort, DrawMethod method = DrawMethod::point, const char* windowTitle = "Sort visualizer" ); 

By providing a single constructor with default parameters, the repetitions are eliminated and flexibility is enhanced. Note also that the array of numbers is passed as an argument.

Reduce the size of the interface to only what is needed

These two functions are generic and don't need to be class members:

std::vector<int> SortVis::loadFile(std::istream& numberFile); std::vector<int> SortVis::generateRandom(int maxNumber); 

By reducing the size of the interface to the minimal needed, the class is smaller and easier to read, understand, test, use, maintain and adapt. Note also that the first argument takes a std::istream& instead of a filename. This allows for such handy things as loading from a socket or a stringstream.

Prefer to fail early

If the SDL_InitSubSystem call in the constructor fails, there's not much point to continuing. For that reason, the more time-consuming calculateNumbers call should probably come after rather than before.

Only set the color if you're going to draw something

The only places that SDL_SetRenderDrawColor should be used is just before something is actually drawn on the screen. For that reason, it can appear exactly twice in this code: once at the top of drawSelection and once at the top of draw.

Move work outside of loops where practical

Instead of recalculating all four portions of column every time through the loop, it's possible to simply change the ones that need to change:

SDL_Rect column{ 0, 0, columnWidth, 0 }; for (const auto n : numbers) { column.h = n * windowSize.Y / maxValue; column.y = windowSize.Y - column.h; SDL_RenderFillRect(renderer, &column); column.x += columnWidth; } 

Use objects instead of switches

The code currently contains this:

void SortVis::Engine::step() { switch (selectedSortAlgorithm) { case SortAlgorithm::bubbleSort: stepBubbleSort(); break; case SortAlgorithm::insertionSort: stepInsertionSort(); break; case SortAlgorithm::selectionSort: stepSelectionSort(); break; default: break; } } 

This requires the evaluation of selectedSortAlgorithm every iteration. The better way to do this is to create a virtual base class that demonstrates the interface and then allow the user to create a derived class with any new kind of sort they like. Here's one way to do it:

using Collection = std::vector<int>; struct Sorter { std::string_view name; virtual bool step(Collection &) = 0; Sorter(Sorter&) = delete; Sorter(std::string_view name) : name{name} { } virtual void reset(Collection& numbers) { a = original_a = 0; original_b = numbers.size(); } virtual ~Sorter() = default; std::size_t a; std::size_t original_a; std::size_t original_b; }; struct BubbleSorter : public Sorter { BubbleSorter() : Sorter{"Bubble Sort"} { } bool step(Collection& numbers) { auto lag{original_a}; for (auto it{lag + 1}; it < original_b; ++it, ++lag) { if (numbers[lag] > numbers[it]) { std::swap(numbers[lag], numbers[it]); } } return ++a != original_b; } }; 

Now for maximum flexibility, you can pass such an object to the Engine in its constructor:

Engine visualization{ { 1024, 768 }, generateRandom(1024), std::make_unique<BubbleSorter>() }; 

Use a pointer to a member function

A similar thing can be done for the drawing method if you like, but it's a little trickier since it uses a pointer to a member function which has a syntax that can be difficult to get right. We might declare the variable within Engine like this:

void (Engine::*drawSelection)(); 

I've repurposed your drawSelection name here. Within the constructor we can use this:

drawSelection{method == DrawMethod::point ? &Engine::drawPoints : &Engine::drawColumns} 

And finally to call it, we need to use the pointer-to-member access operator. Here it is in context:

void SortVis::Engine::draw() { // Sets render draw color to black SDL_SetRenderDrawColor(renderer, 0, 0, 0, 255); SDL_RenderClear(renderer); SDL_SetRenderDrawColor(renderer, 255, 255, 255, 255); (this->*(drawSelection))(); SDL_RenderPresent(renderer); } 

Don't do work that isn't needed

Right now, the main loop in run is this:

while (running) { handleEvents(); if (!std::is_sorted(numbers.begin(), numbers.end())) { step(); } draw(); } 

It doesn't make much sense to me to make a call to std::is_sorted within a program that demonstrates sorting! It seemed to me that I'd want to close the program when it was done sorting and I modified the sorting routines to return bool with value of false only when it's finished running and the vector is sorted. So for that, the loop turns into this:

while (running) { handleEvents(); running &= sorter->step(numbers); draw(); } 

Consider adding features

I'd suggest that it might be nice to add some features. Here's what I did:

void SortVis::Engine::handleEvents() { SDL_Event Event; while (SDL_PollEvent(&Event)) { switch (Event.type) { case SDL_QUIT: running = false; break; case SDL_KEYDOWN: switch (Event.key.keysym.sym) { case SDLK_r: numbers = generateRandom(maxValue); sorter->reset(numbers); break; case SDLK_b: numbers = generateRandom(maxValue); sorter = std::move(std::make_unique<BubbleSorter>()); sorter->reset(numbers); break; case SDLK_i: numbers = generateRandom(maxValue); sorter = std::move(std::make_unique<InsertionSorter>()); sorter->reset(numbers); break; case SDLK_s: numbers = generateRandom(maxValue); sorter = std::move(std::make_unique<SelectionSorter>()); sorter->reset(numbers); break; case SDLK_l: drawSelection = &Engine::drawColumns; break; case SDLK_p: drawSelection = &Engine::drawPoints; break; case SDLK_q: running = false; break; } default: break; } } } 

Answer 2

Use namespace SortVis {...} in Engine.cpp

You can avoid repeating the namespace in each function definition in Engine.cpp by wrapping all the code inside namespace SortVis, just like you did in Engine.h. It's also common to not indent the code inside a namespace {...} block that covers the whole file, to avoid code running off the right hand of the screen too often.

Too many constructors

You have 12 different constructors, that is a bit much. Also imagine that you might want to add another optional parameter in the future, then you double the number of constructors required. This is not maintainable in the long run. I see two ways to cut down the number of constructors required:

1. Use default argument values, like so:

   Engine(Coord windowSize, int maxNumber, const char *windowTitle = "Sort visualizer", SortAlgorithm algorithm = SortAlgorithm::bubbleSort, DrawMethod method = DrawMethod::line); 

   With this approach, you only need two constructors. It might be slightly more annoying to use if you only want to specify another DrawMethod, but it is a small price for much improved maintainablility.

2. Don't specify the input values, algorithm and drawing method in the constructor, allow these to be set by member functions, like so:

   Engine(Coord windowSize, const char *windowTitle = "Sort visualizer"); void generateNumbers(int maxNumber); void loadNumbers(const char *pathToNumbersFile); void setAlgorithm(SortAlgorithm algorithm); void setDrawMethod(DrawMethod method); 

In general, only do in the constructor what really needs to be done at construction time. Initializing SDL and opening a window is crucial to a working visualization engine, so that is good to do in the constructor.

Consider not generating/loading numbers in class Engine

Instead of having Engine generate random numbers or load them from a file, you can simplify it by not doing that at all, but rather just allow it to use any vector that you give it. So for example:

void run(const std::vector<int> &input) { numbers = input; ... } 

You can even consider passing it as non-const, and have run() modify the given input vector.

Consider splitting visualization from sorting

A big issue is that you have to split your sorting algorithms into steps, and have a switch() statement in step() to pick the right algorithm. You also need to enumerate the possible algorithms. Instead of doing that, consider making Engine just visualize a vector of numbers, and instead of Engine driving the steps of the algorithm, have an algorithm drive Engine to show the state of the vector at each step. You can do this by changing Engine::draw() to take a reference to a vector of numbers:

void Engine::draw(const std::vector<int> &numbers) { ... } 

And a sorting algorithm can just become a single function:

void bubbleSort(std::vector<int> &numbers, Engine &visualization) { for (size_t i = 0; i < numbers.size() - 1; ++i) { for (size_t j = 0; j < numbers.size() - 1; ++j) { if (numbers[j] > numbers[j + 1])) { std::swap(numbers[j], numbers[j + 1]); } } visualization.draw(numbers); } } 

And then your main() could look like so:

int main() { std::vector<int> numbers = {...}; // generate some vector here SortVis::Engine visualization({1024, 768}); SortVis::bubbleSort(numbers, visualization); } 

The benefits to this approach are that you separate concerns. The Engine now only has to visualize a vector (it probably should be renamed to something like Visualizer). You can easily add new sorting algorithms without having to change Engine.

One issue with the above is that it no longer handles SDL events. You could do this in draw(), and have draw() return a bool indicating whether the algorithm should continue or not.

Check for errors after reading a file, not before

In Engine::loadFile(), you check whether the file is opened correctly, but you never check whether there was an error during reading. A possible way is:

std::ifstream NumbersFile(pathToNumbersFile); std::string Number; while (std::getline(NumbersFile, Number) { numbers.push_back(std::stoi(Number)); } if (!NumbersFile.eof()) { throw std::runtime_error("Error while reading numbers file."); } 

Here we use the fact that the eofbit is only set if it succesfully reached the end of the file, it will not be set if the file failed to open or if an error occurred before reaching the end of the file.