alesbe/sorting-visualizer

Sorting visualizer made with SFML and C++ 📊

📊 Sorting Visualizer

A lightweight sorting visualizer made with C++ and SFML.

Quick sort

Bubble sort

Bubble sort info

📖 I want to contribute to the project!

Awesome! Here you can find some useful info about the visualizer, we accept first contributors too!

Also, make sure to pull the last changes from dev branch!

🗂️ Sort types

• Bubble sort
  • Bubble sort works by continuously swapping elements next to each other that are in the wrong place. Starting from the beginning of the dataset, each element 'floats' to its correct spot. More on Bubble sort can be found here.
• Selection sort
  • Selection sort works by having two sections, the sorted and unsorted sections, and continuously search through the unsorted section and place the smallest element into the sorted section. This sorting algorithm could be implemented where the largest element is selected instead. More on selection sort can be found here.
• Insertion sort
  • Insertion sort is similar to selection sort in that they both have a sorted and unsorted section. Instead of continuously selected the smallest/largest element, it will insert a selected element from the unsorted portion and 'insert' it into the correct spot in the sorted section. More on insertion sort can be found here.
• Quick sort
  • Quick sort is a "Divide and Conquer" algorithm. Divide and Conquer algorithms work by splitting the problem into smaller portions, solving the smaller problems, then combing the solutions into one final solution. Quick sort works by choosing an element as a 'pivot', moving the other elements around where elements less than the pivot are on one side and elements greater than the pivot are on the other, then continuously doing that process with each side. Once each element has been partitioned, the solution is combined into the sorted array. More on quick sort can be found here and more on Divide and Conquer algorithms can be found here.
• Cocktail shaker sort
  • Cocktail shaker sort is a variant of Bubble Sort. Instead of only having elements 'float' from the bottom to its correct spot in the dataset, elements also 'sink' from the top of the datset into its correct position. More on cocktail shaker sort can be found here.
• Bogo sort
  • Bogo sort is an inefficient sorting algorithm where it randomly generates different versions of the original dataset and checks if it's sorted or not. More on bogo sort can be found here.
• Bitonic sort
  • Bitonic sort is a comparison based sorting algorithm that can be run with parallel implementation. Within different subarrays, the algorithm checks if the first element is smaller than the second and vice versa. It continuously does that on larger subarrays until the whole dataset is sorted. More on bitonic sort can be found here.

🕹️ Usage

• Space: Start sort
  
• Backspace: Stop sort
  
• h: Display help
  
• F1: Change number of elements
  
• F2: Change time between comparisons
  
• Arrow Up / Arrow down: Change sort type
  

🖨️ Download

Requirements:

• CMake

🐧 Linux

• Clone the project: git clone https://github.com/alesbe/sorting-visualizer && cd sorting-visualizer
• Run ./install.sh

🖥️ Windows / MacOS

Download from releases

If you want to compile the project by yourself you need to follow the next steps:

1. Download SFML from the official website
2. Download CMake
3. Clone the repository
4. Open CMakeLists.txt and locate the variable SFML_DIR. Set the path to the route where the SFML CMake files are located. For instance C:/Program Files (x86)/SFML/lib/cmake/SFML.
5. From the root directory of the repository, run:

mkdir build cd build
cmake ..
cmake -G 'Visual Studio 17 2022' ..

6. In the /build directory should be a Visual Studio solution. Now you can open the solution and compile the file with the play button as usual!

Note: If you don't want to use Visual Studio 2022, download SFML for your target compiler and change the cmake generator in step 6. You can check the list of generators with cmake -G

sorting-visualizer's Issues

[BUG]: Stopping some algorithms bugs the visualizer

Describe you problem / suggestion:

Stopping Quick Sort does not stop the algorithm, it continues trying to sort in a weird way and after a while, the algorithm finishes.

Steps to reproduce (optional):

• Select Quick Sort
• Press space and then backspace

Possible fix (optional):

Pressing backspace only clears and populates the array with sorted elements. Maybe we should change how the algorithm is stopped. (Joining the thread instead of detaching it?)

OS

• : Windows
• : Mac OS
• : Linux

Loading a sortType that doesn't exists stops the program

Describe your problem:

When you try to select a sorting algorithm that does not exists and load it, the program just stops and can't do anything. Restarting the program solves the issue.

Steps to reproduce:

• Select a non-defined algorithm with the arrow keys and start pressing space

Possible fix (optional):

Make sure that sortType it's associated to a sorting algorithm in sf::Keyboard::Up and sf::Keyboard::Down events, in main.cpp

OS

• Windows
• Mac OS
• Linux

Add SFML libraries for Windows and MacOS

Describe you problem / suggestion:

CMake works as expected on Linux, but on Windows or macOS the project can't be build because the SFML libraries included with the project are only for Linux (GCC), so CMake can't be used on Windows or macOS.

Steps to reproduce (optional):

• Clone the repository and try to build the project using CMake: cmake -G "MinGW Makefiles" CMakeLists.txt in Windows or macOS.

Possible fix (optional):

Im not sure how to approach this issue, maybe adding libraries for Windows, Linux and macOS and detecting the OS in CMakeLists.txt, so the correct libraries can be included.

OS

• : Windows
• : Mac OS
• : Linux

[BUG]: errors while trying to generate MinGW makefile with CMake on windows

Describe you problem:

Windows users may need to use MinGW with CMake to compile the program. When generating a makefile for the sorting-visualizer using mingw32-make the following errors are thrown:

\sorting-visualizer\src\SortController.cpp: In member function 'void SortController::_startSort(int)':
\sorting-visualizer\src\SortController.cpp:144:71: error: no matching function for call to 'std::thread::thread(void (SortController::*)(), SortController*)'
  144 |         _animThread = std::thread(&SortController::checkSortAnim, this);
      |                                                                       ^
In file included from C:/mingw64/lib/gcc/x86_64-w64-mingw32/12.2.0/include/c++/thread:43,
                 from \sorting-visualizer\src\SortController.h:10,
                 from \sorting-visualizer\src\SortController.cpp:1:
C:/mingw64/lib/gcc/x86_64-w64-mingw32/12.2.0/include/c++/bits/std_thread.h:156:5: note: candidate: 'std::thread::thread(std::thread&&)'
  156 |     thread(thread&& __t) noexcept
      |     ^~~~~~
C:/mingw64/lib/gcc/x86_64-w64-mingw32/12.2.0/include/c++/bits/std_thread.h:156:5: note:   candidate expects 1 argument, 2 provided
C:/mingw64/lib/gcc/x86_64-w64-mingw32/12.2.0/include/c++/bits/std_thread.h:120:5: note: candidate: 'std::thread::thread()'
  120 |     thread() noexcept = default;
      |     ^~~~~~
C:/mingw64/lib/gcc/x86_64-w64-mingw32/12.2.0/include/c++/bits/std_thread.h:120:5: note:   candidate expects 0 arguments, 2 provided
\sorting-visualizer\src\SortController.cpp: In member function 'void SortController::startSort(int)':
\sorting-visualizer\src\SortController.cpp:165:81: error: no matching function for call to 'std::thread::thread(void (SortController::*)(int), SortController*, int&)'
  165 |         _sortingThread = std::thread(&SortController::_startSort, this, sortType);
      |                                                                                 ^
C:/mingw64/lib/gcc/x86_64-w64-mingw32/12.2.0/include/c++/bits/std_thread.h:156:5: note: candidate: 'std::thread::thread(std::thread&&)'
  156 |     thread(thread&& __t) noexcept
      |     ^~~~~~
C:/mingw64/lib/gcc/x86_64-w64-mingw32/12.2.0/include/c++/bits/std_thread.h:156:5: note:   candidate expects 1 argument, 3 provided
C:/mingw64/lib/gcc/x86_64-w64-mingw32/12.2.0/include/c++/bits/std_thread.h:120:5: note: candidate: 'std::thread::thread()'
  120 |     thread() noexcept = default;
      |     ^~~~~~
C:/mingw64/lib/gcc/x86_64-w64-mingw32/12.2.0/include/c++/bits/std_thread.h:120:5: note:   candidate expects 0 arguments, 3 provided
mingw32-make[2]: *** [CMakeFiles\sorting-visualizer.dir\build.make:121: CMakeFiles/sorting-visualizer.dir/src/SortController.cpp.obj] Error 1
mingw32-make[1]: *** [CMakeFiles\Makefile2:82: CMakeFiles/sorting-visualizer.dir/all] Error 2
mingw32-make: *** [Makefile:90: all] Error 2

Steps to reproduce (optional):

• clone the directory on windows using git clone https://github.com/alesbe/sorting-visualizer && cd sorting-visualizer
• install CMake version 3.25.1
• navigate to the root directory of the above cloned repository on local machine
• Set up gcc and g++ compilers using (installation path may vary):

CMake -DCMAKE_C_COMPILER="C:/mingw64/bin/gcc.exe"
CMake DCMAKE_CXX_COMPILER="C:/mingw64/bin/g++.exe"

• run CMake -G "MinGW Makefiles"
• Build files get written to /sorting-visualizer
• run mingw32-make
• errors above occur at this point

Additional info (optional):

Running Windows 11
gcc.exe (x86_64-win32-sjlj-rev0, Built by MinGW-W64 project) 12.2.0
g++.exe (x86_64-win32-sjlj-rev0, Built by MinGW-W64 project) 12.2.0

OS

• : Windows
• : Mac OS
• : Linux

Adding OS detection and install dependencies with install.sh

Describe you problem / suggestion:

Installing automatically the required dependencies (sfml), with install.sh would be easier that installing the dependencies manually.

Steps to reproduce (optional):

none

Possible fix (optional):

• Option 1: The sfml packages is available at least in Debian/Ubuntu and Arch (I didn't check more OS's), detect the distribution and install sfml using the default packet manager.
• Option 2: Adding the SFML libraries to the project and compile with Makefile.

OS

• : Windows
• : Mac OS
• : Linux

[BUG]: Source code doesn't compile.

Describe you problem:

Source code doesn't compile.

Steps to reproduce (optional):

install.sh

Additional info (optional):

sorting-visualizer/src/SortController.h:27:33:

error: copying member subobject of type 'std::atomic' invokes deleted constructor
std::atomic _interrupt = false;

sorting-visualizer/src/SortAlgorithms.cpp:215:11:

error: out-of-line definition of 'bogoSort' does not match any declaration in namespace 'algo'
int algo::bogoSort(std::vector& sortElements, int timeSleep)

Possible fix (optional):

std::atomic _interrupt = { false };
Add required argument to bogosort

OS

• : Windows
• : Mac OS
• : Linux

Add CMake or Makefile to compile the libraries

Describe you problem / suggestion:

The install.sh script installs the sfml library from the distro packet manager, but it would be nice to use the sfml libraries included with the project in the /lib folder. Also, using CMake or Makefile will add support for Windows and MacOS.

Steps to reproduce (optional):

None

Possible fix (optional):

• Option 1: Fix the current Makefile to compile the libraries and the source code into a single executable.
• Option 2: Use CMake instead of Makefile for the same purpose.

OS

• : Windows
• : Mac OS
• : Linux

Add contributors to readme

This issue is just for adding contributors to readme, thanks to everyone!

Add Windows and MacOS support via CMake or Makefile

Describe you problem / suggestion:

Right now the Linux install via install.sh works perfect, but for Windows and MacOS you need to build yourself the binary.

Steps to reproduce (optional):

None

Possible fix (optional):

Add any installation method for Windows and MacOS using CMake or similar, something that compiles the .cpp files from /src and include the sfml library located in /lib.

OS

• : Windows
• : Mac OS
• : Linux

Possible data race

There appears to be a shared resource between threads without any kind of locking/access control. I fear this may lead to data races. (Mind my relative inexperience with parallel programming.)

[edit: the correct term is "race condition"]

On main:

sorting-visualizer/main.cpp

Line 135 in 72efc53

for (auto sortable : sortController.sortElements) {

Also here among other points of access:

sorting-visualizer/main.cpp

Line 108 in 72efc53

sortController.clear();

On sorting worker:

sorting-visualizer/SortController.cpp

Line 72 in 72efc53

numOfComparisons += algo::bubbleSort(sortElements, timeSleep);

The worker thread could still be writing the elements in the sort container while main is reading it. Main could then end up with an invalid object/data.

A simple way to reproduce this is to hit F1 immediately after beginning a sort (bubble in my case). Where the worker will then try to access elements that are no longer there. I worry that danger maybe present in line 135 on main, even if it's unlikely.

(Anyhow hope this issue is helpful/useful.)

[FEAT]: The visualizer needs more sorting algorithms

Describe your problem:

Right now there is only 3 sorting algorithms, would be so cool to add more!

Steps to reproduce:

None

Possible fix (optional):

Add new sorting algorithms (how to add new algorithms)

OS

• Windows
• Mac OS
• Linux

Incorrect name for selection sort

Code for selection sort algoritm is exchange sort logic.

Make an install.sh for Linux / macOS

Issue/Suggestion description

Would be cool to add an install.sh that installed the sfml package, compile the project, and move the executable to /usr/bin, so it can be directly launched.

Possible fix (optional)

I tried to implement this, and works as expected, the only issue is that when I try to execute it using rofi, (i suppose that happens the same with other application launchers), only the SFML window shows up, and the terminal window is also needed for changing the configurations and displaying the sort info.

A possible fix can be to open a separated terminal when the program launches or implementing a pop-up menu, I really like the minimal style of the visualizer, so adding text on top can interfere with that!

OS

• Windows
• MacOS
• Linux

Clean CMake files after building

Describe you problem / suggestion:

CMake generates a lot of files while building, it would be nice to generate those files in a temporary folder and then remove it using install.sh when the build is completed.

Steps to reproduce (optional):

None

Possible fix (optional):

Edit install.sh and/or CMakeLists.txt to not generate all the files in the root directory.

OS

• : Windows
• : Mac OS
• : Linux

[DOC]: Update wiki

Documentation description:

With the changes from #24, the wiki should be updated with the changes.