19
\$\begingroup\$

I finished a sorting algorithm visualizer (for now only uses bubble sort) and this is the code. I'd like some suggestions to improve the memory usage or time elapsed. Built with Cmake and Ninja on Windows

Demonstration

Demonstration

main.cpp

#include "Engine.h"
#undef main

int main()
{
    try
    {
        // if the amount is higher than the screen width it draws nothing other than a black screen :^)
        SortVis::Engine Visualization({ 1024, 768 }, 1024);
        Visualization.Run();
    }
    catch (std::runtime_error& Error)
    {
        std::cerr << Error.what() << "\n";
    }
}

Engine.h

#pragma once

#include "Coord.h"
#include <SDL.h>
#include <vector>
#include <iostream>

namespace SortVis
{
    class Engine
    {
    public:

        Engine() = delete;
        Engine(Coord pWindowSize, int pMaxNumber);
        Engine(Coord pWindowSize, const char* pPathToNumbersFile);
        Engine(Coord pWindowSize, const char* pPathToNumbersFile, const char* pWindowTitle);
        Engine(Coord pWindowSize, int pMaxNumber, const char* pWindowTitle);

        ~Engine();

        void Run();

    private:

        const Coord m_WindowSize;
        SDL_Window* m_Window = nullptr;
        SDL_Renderer* m_Renderer = nullptr;
        
        std::vector<int> m_Numbers = { };
        int m_ColumnWidth = 0;
        int m_MaxValue = 0;
        bool m_Running = true;
        bool m_Sorted = false;

        void InitWindow(Coord pWindowSize, const char* pWindowTitle);
        void InitRenderer();
        void CalculateNumbers();        
        void LoadFile(const char* pPathToNumbersFile);
        
        void HandleEvents();
        void BubbleSort();
        void Draw();
        void DrawColumns();

        void GenerateRandom(int pMaxNumber);        
    };
}

Engine.cpp

#include "Engine.h"

#include <filesystem>
#include <fstream>
#include <random>
#include <utility>
#include <algorithm>
#include <string>

SortVis::Engine::Engine(Coord pWindowSize, int pMaxNumber)
    : m_WindowSize(pWindowSize)
{
    GenerateRandom(pMaxNumber);

    CalculateNumbers();

    if (SDL_InitSubSystem(SDL_INIT_VIDEO) < 0)
    {
        throw std::runtime_error("Could not initialize SDL");
    }

    InitWindow(pWindowSize, "Sort visualizer");
    InitRenderer(); 
}

SortVis::Engine::Engine(Coord pWindowSize, int pMaxNumber, const char* pWindowTitle)
    : m_WindowSize(pWindowSize)
{
    GenerateRandom(pMaxNumber);

    CalculateNumbers();

    if (SDL_InitSubSystem(SDL_INIT_VIDEO) < 0)
    {
        throw std::runtime_error("Could not initialize SDL");
    }

    InitWindow(pWindowSize, "Sort visualizer");
    InitRenderer();
}

SortVis::Engine::Engine(Coord pWindowSize, const char* pPathToNumbersFile)
    : m_WindowSize(pWindowSize)
{
    if (!std::filesystem::exists(pPathToNumbersFile))
    {
        throw std::runtime_error("That file does not exist. Make sure the path is correct.");
    }
    else
    {
        LoadFile(pPathToNumbersFile);
    }
    CalculateNumbers();

    if (SDL_InitSubSystem(SDL_INIT_VIDEO) < 0)
    {
        throw std::runtime_error("Could not initialize SDL");
    }

    InitWindow(pWindowSize, "Sort visualizer");
    InitRenderer();
}

SortVis::Engine::Engine(Coord pWindowSize, const char* pPathToNumbersFile, const char* pWindowTitle)
    : m_WindowSize(pWindowSize)
{
    if (!std::filesystem::exists(pPathToNumbersFile))
    {
        throw std::runtime_error("That file does not exist. Make sure the path is correct.");
    }
    else
    {
        LoadFile(pPathToNumbersFile);
    }
    CalculateNumbers();

    if (SDL_InitSubSystem(SDL_INIT_VIDEO) < 0)
    {
        throw std::runtime_error("Could not initialize SDL");
    }

    InitWindow(pWindowSize, pWindowTitle);
    InitRenderer();
}

SortVis::Engine::~Engine()
{
    SDL_DestroyWindow(m_Window);
    SDL_DestroyRenderer(m_Renderer);

    SDL_Quit();
}

void SortVis::Engine::Run()
{
    // Sets render draw color to black
    SDL_SetRenderDrawColor(m_Renderer, 0, 0, 0, 255);
    Draw();

    while (m_Running)
    {
        HandleEvents();
        if (!m_Sorted)
        {
            BubbleSort();
        }
    }
}

void SortVis::Engine::BubbleSort()
{   
    for (int i = 0, Size = m_Numbers.size(); i < Size - 1; ++i)
    {
        for (int j = 0; j < Size - i - 1; ++j)
        {
            HandleEvents();
            if (!m_Running)
            {
                return;
            }

            if (m_Numbers[j] > m_Numbers[j + 1])
            {
                std::swap(m_Numbers[j], m_Numbers[j + 1]);
            }           
        }

        Draw();
    }
    
    m_Sorted = true;
}

void SortVis::Engine::Draw()
{
    SDL_RenderClear(m_Renderer);

    DrawColumns();

    SDL_RenderPresent(m_Renderer);
}

void SortVis::Engine::DrawColumns()
{
    SDL_SetRenderDrawColor(m_Renderer, 255, 255, 255, 255);

    SDL_Rect Column;
    for (int i = 0, Size = m_Numbers.size(); i < Size; ++i)
    {
        Column.x = i * m_ColumnWidth;
        Column.w = m_ColumnWidth;
        Column.h = (m_Numbers[i] * m_WindowSize.Y) / m_MaxValue;
        Column.y = m_WindowSize.Y - Column.h;
        SDL_RenderFillRect(m_Renderer, &Column);
    }

    SDL_SetRenderDrawColor(m_Renderer, 0, 0, 0, 255);
}

void SortVis::Engine::HandleEvents()
{
    SDL_Event Event;

    while (SDL_PollEvent(&Event))
    {
        switch (Event.type)
        {
        case SDL_QUIT:
            m_Running = false;
            break;
        }
    }
}

void SortVis::Engine::GenerateRandom(int pMaxNumber)
{
    std::mt19937 Seed(std::random_device{}());
    std::uniform_int_distribution<int> Distribution(1, pMaxNumber);

    for (int i = 0; i < pMaxNumber; ++i)
    {
        int Number = Distribution(Seed);
        while (std::count(m_Numbers.begin(), m_Numbers.end(), Number) != 0)
        {
            Number = Distribution(Seed);
        }
        m_Numbers.push_back(Number);
    }
    std::cout << "Generated random number sequence.\n";
}

void SortVis::Engine::CalculateNumbers()
{
    m_ColumnWidth = m_WindowSize.X / m_Numbers.size();
    m_MaxValue = *std::max_element(m_Numbers.begin(), m_Numbers.end());
}

void SortVis::Engine::LoadFile(const char* pPathToNumbersFile)
{
    std::ifstream NumbersFile(pPathToNumbersFile);
    if (NumbersFile.is_open())
    {
        std::string Number;
        while (std::getline(NumbersFile, Number))
        {
            m_Numbers.push_back(std::stoi(Number));
        }
    }
    else
    {
        throw std::runtime_error("Couldn't open numbers file.");
    }

    if (m_Numbers.empty())
    {
        throw std::runtime_error("Numbers file is empty.");
    }

    std::cout << "Loaded numbers file.\n";
}

void SortVis::Engine::InitWindow(Coord pWindowSize, const char* pWindowTitle)
{
    m_Window = SDL_CreateWindow(
        pWindowTitle,
        SDL_WINDOWPOS_UNDEFINED,
        SDL_WINDOWPOS_UNDEFINED,
        pWindowSize.X,
        pWindowSize.Y,
        SDL_WINDOW_SHOWN
    );

    if (m_Window == nullptr)
    {
        throw std::runtime_error("Could not initialize SDL window");
    }
}

void SortVis::Engine::InitRenderer()
{
    m_Renderer = SDL_CreateRenderer(
        m_Window,
        -1,
        SDL_RENDERER_PRESENTVSYNC | SDL_RENDERER_ACCELERATED
    );

    if (m_Renderer == nullptr)
    {
        throw std::runtime_error("Could not initialize SDL renderer");
    }
}

Coord.h

#pragma once

namespace SortVis
{
    struct Coord
    {
        int X;
        int Y;
    };
}
\$\endgroup\$
  • 4
    \$\begingroup\$ Note on the demonstration: The actual program runs a lot faster (10s to sort on a VM), however, my screen recording in the VM was a little bit sluggish and I accidentally didn't use the correct speed-up factor to fix the issue in post-processing. That being said you should probably add how you compiled your application, given that it uses both SDL2 as well as C++17. That eases simple tests for reviewers. \$\endgroup\$ – Zeta Aug 13 at 15:52
  • \$\begingroup\$ I added the way i built the executable. If you want to know the build options i passed tell me and i'll also post my CMakeLists.txt file \$\endgroup\$ – Nadpher Aug 13 at 16:32
  • 2
    \$\begingroup\$ @Zeta No worries, the demo actually looks a lot better this way. \$\endgroup\$ – Mast Aug 13 at 16:34
  • 2
    \$\begingroup\$ It'd be cool to see this on GitHub with the build system in place. I'd like to try it out with any advice from the reviews implemented. \$\endgroup\$ – S.S. Anne Aug 14 at 0:13
  • \$\begingroup\$ github.com/Nadpher/SortVisualization here is the github, if you want the newer version with the improvements from the answers you'll have to clone the dev branch \$\endgroup\$ – Nadpher Aug 14 at 8:08
14
\$\begingroup\$

In all, this is a nice program. In particular, it compiled and ran (almost) flawlessly on Linux, so keep up the good work on portability! Here are some things that may help you improve your program.

Fix the bug

It's a subtle bug, but there is a problem with the Engine class. The destructor is this:

SortVis::Engine::~Engine()
{
    SDL_DestroyWindow(m_Window);
    SDL_DestroyRenderer(m_Renderer);

    SDL_Quit();
}

However, m_Renderer contains a reference to m_Window as we can see from this part of InitRenderer():

m_Renderer = SDL_CreateRenderer(
    m_Window,
    -1,
    SDL_RENDERER_PRESENTVSYNC | SDL_RENDERER_ACCELERATED
);

For that reason, the SDL_DestroyRenderer() call must come first.

Use include guards

There should be an include guard in each .h file. That is, start the file with:

#ifndef ENGINE_H
#define ENGINE_H
// file contents go here
#endif // ENGINE_H

The use of #pragma once is a common extension, but it's not in the standard and thus represents at least a potential portability problem. See SF.8

Reconsider your naming convention

One common convention is the use uppercase for all classes and structures and lowercase for instances or individual variable names. This code seems to use uppercase for everything. Also, the partial use of "Hungarian notation" here is not recommended. See NL.5 for details.

Separate algorithm and user I/O

The question notes that only BubbleSort is currently implemented, but it's clear your intent is to add other algorithms. For that reason, I'd suggest refactoring the Engine class so that instead of having the algorithm and the display and user I/O handing all contained within a BubbleSort member function, I would suggest rewriting so that Engine would repeatedly call a step function that would advance one step in a sorting algorithm. That function would be solely concerned with the actual sorting mechanics, while the Engine would take care of all of the user I/O.

Simplify for loops by counting down

The code currently has this loop in DrawColumns():

for (int i = 0, Size = m_Numbers.size(); i < Size; ++i)
{
    Column.x = i * m_ColumnWidth;
    // etc.
}

However, this is an instance in which we don't really care whether we're counting up or down as long as all columns are displayed. With that in mind, I'd suggest writing it like this:

for (int i = m_Numbers.size(); i; --i)
{
    Column.x = (i-1) * m_ColumnWidth;
    // etc.
}

As @Useless suggested in a comment, it's not too pretty to have to subtract 1 from i within the loop to use it.

Better would be the next suggestion.

Simplify using a range-for

The same code loop can be simplified a bit further.

void SortVis::Engine::DrawColumns()
{
    SDL_SetRenderDrawColor(m_Renderer, 255, 255, 255, 255);

    SDL_Rect Column{ 0, 0, m_ColumnWidth, 0};
    for (const auto n : m_Numbers)
    {
        Column.h = n * m_WindowSize.Y / m_MaxValue;
        // uncomment this to make the picture identical to the original
        // Column.y = m_WindowSize.Y - Column.h;
        SDL_RenderFillRect(m_Renderer, &Column);
        Column.x += m_ColumnWidth;
    }

    SDL_SetRenderDrawColor(m_Renderer, 0, 0, 0, 255);
}

This version inverts the picture so that the bars are anchored to the bottom instead of the top of the image. If you prefer it as it was originally done, just uncomment the code line.

Simplify by better using standard algorithms

The GenerateRandom code is a lot more complex than it needs to be. You could write it like this:

void SortVis::Engine::GenerateRandom(int pMaxNumber)
{
    static std::mt19937 rng(std::random_device{}());
    std::vector<int> num(pMaxNumber);
    std::iota(num.begin(), num.end(), 0);
    std::shuffle(num.begin(), num.end(), rng);
    std::swap(num, m_Numbers);
}

An alternative approach that I like even better is this:

static std::vector<int> generateRandom(int pMaxNumber)
{
    static std::mt19937 rng(std::random_device{}());
    std::vector<int> num(pMaxNumber);
    std::iota(num.begin(), num.end(), 0);
    std::shuffle(num.begin(), num.end(), rng);
    return num;
}

Now we can simplify the constructor for Engine. Instead of this:

SortVis::Engine::Engine(Coord pWindowSize, int pMaxNumber)
    : m_WindowSize(pWindowSize)
{
    GenerateRandom(pMaxNumber);
    // etc.
}

Write this:

SortVis::Engine::Engine(Coord pWindowSize, int pMaxNumber)
    : m_WindowSize(pWindowSize),
    m_Numbers{generateRandom(pMaxNumber)}
{
    // etc.
}

Don't ignore passed variables

The only difference between the two constructors for Engine is that one of them allows the user to passed a window title, which is then ignored! Better would be to use just the version the allows the window title and then set a default value for it.

| improve this answer | |
\$\endgroup\$
  • 3
    \$\begingroup\$ Note that looping upwards is common and quicker for many people to read and be 100% sure of the loop bounds. Also, if you're indexing any arrays, hardware prefetch may work at least slightly better when looping forwarding (increasing addresses). e.g. in Intel CPUs, the main L2 streamer can handle either direction, but one of the other prefetchers (perhaps L1d IIRC) doesn't work as well with decreasing addresses. (OTOH, if you just looped upward in one loop, the end of the array will be hot in cache so looping backwards in the next pass over the array can be good, if you don't cache-block it) \$\endgroup\$ – Peter Cordes Aug 14 at 0:44
  • 3
    \$\begingroup\$ @PeterCordes I usually value clarity over performance and then find I am often pleased to find that what is clear to me also runs faster. It's good to note that which is faster is often hardware-dependent; which is clearer is often less so. Measuring is always good. \$\endgroup\$ – Edward Aug 14 at 1:17
  • 1
    \$\begingroup\$ I'm not a fan of using the wrong value for a loop counter and having to subtract one: it's easy to add a usage of i instead of i-1 by mistake. for (int i = m_Numbers.size(); i--; ) makes the body simpler, but the loop condition itself feels more brittle (it's easy not to notice the post-decrement). I'm not sure either is an improvement over the original. \$\endgroup\$ – Useless Aug 14 at 14:31
  • \$\begingroup\$ @Useless: I agree that's a good suggestion. What I actually did in my own refactor was to initialize the SD_Rect outside the loop and then adjust it within the loop since Column.w and Column.y are loop invariant in my version. \$\endgroup\$ – Edward Aug 14 at 15:22
  • \$\begingroup\$ @Useless Why exactly would you misread i-- for --i ? \$\endgroup\$ – clockw0rk Aug 14 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.