How to add a new sorting algorithm

If you want to add a new sorting algorithm to the project, that's great! This is probably one of the easiest and useful contributions that you can do, so let's dive in!

1.- Things to know before adding a new algorithm

• Check if the algorithm that you want to include isn't already in the project (Check readme, Utils.h or SortingAlgorithms.h).

2.- Declaring the algorithm

The best way to learn something it's by example, so let's see how a bubble sort algorithm is added:

Add the new function to SortAlgorithms.h and SortAlgorithms.cpp

First, let's do the declaration in SortAlgorithms.h

namespace algo {
	int bubbleSort(std::vector<Sortable>& sortElements, int timeSleep); // Our new algorithm
}

And now, let's declare the function in SortAlgorithms.cpp

int algo::bubbleSort(std::vector<Sortable>& sortElements, int timeSleep) {
	return 0;
}

As you can see, every function takes a reference to the vector that is going to be sorted, and a timeSleep, that is the time that we are going to wait between each comparison

Add a new switch case to SortController::startSort()

When the user starts the sorting process, startSort() it's called, and depending on the sortType it's going to execute one algorithm or another, so we are going to make a new switch case for our new algorithm, just go to SortController.cpp and add a new one just before default case:

void SortController::startSort(int sortType) {
	while (!isSorted())
	{
		switch (sortType)
		{
		...
		// Our new case, use the next sortType available
		case 17:
			numOfComparisons += algo::bubbleSort(sortElements, timeSleep); // Our new algorithm
			break;
		default:
			return;
		}
	}
}

As you can see, we add the function return to numOfComparisons. When the array is sorted, will be displayed the total number of comparisons that the algorithm made.

Add a new switch case to Utils::getSortType()

And last but not least, we are going to add our new sortType to getSortType(), this function is used to translate the sortType int, to the real sort type, formated in a string. Go to Utils.cpp and add your new algorythm:

std::string Utils::getSortType(int sortType) {
	switch (sortType)
	{
	. . .
	// Make sure to use the same sortType int that we defined in SortController::startSort()!
	case 17:
		return "Insertion sort"; // Sort name

	default:
		return std::to_string(sortType);
	}
}

Great! Now, compile the visualizer and press the arrow key up to change the algorithm and you should see your new sorting algorithm, cool! But, right now doesn't do anything, so let's add the functionality!

3.- Defining the algorithm

Every algorithm function does 3 things:

• Sort the elements vector
• Change the color of the element compared to red, and after the comparison is made, change it to white.
• Increment the number of comparisons

All the logic will be inside our function, the one that we defined in SortingAlgorithms.cpp. Every function takes 2 arguments: std::vector<Sortable>& sortElements, and int timeSleep. The first one is the vector containing the elements that we are going to sort, it's a reference to sortElements, a vector contained in the SortController object. The second one is the milliseconds that we're going to wait between each comparison.

Sorting

Before proceding, you need to know that the function it's looped inside SortController::startSort() until the vector is sorted, do you don't need to define a while loop inside the function to check if is sorted.

The sorting process per se, it's different for every sorting algorithm. Each element of the vector contains a value int attached to it, that helps us to make the process easier, but be carefull! We dont want to swap the values of the elements, we want to swap the element position inside the vector, swapping the values would not do anything.

If your algorithm uses swapping, I made a function to make everything easier, it manages the swapping and also the color changing too, so you just need to call the function when necessary and increment numOfComparisons on each comparison. The function is defined in the same file but in a different namespace, so you dont need to import anything, just call the function like this:

algoUtils::swap(sorting_vector, time_sleep, element_1, element_2);

If you don't use swapping in your algorithm, swap the elements manually storing one element in a temporary variable.

I recommend to try if the algorithm is being sorted and displayed correctly before moving on, if everything works as intended, let's continue!

Changing colors

If you used algoUtils::swap() in your function, you can skip this part, because the function manages also the color changing, if not, let's see how to change the colors!

This part is purely visual, but it's one of my favourites, because allows you to actually see what is swapping. To achieve that, we'll change the color value of the element being swapped. SFML uses it's own types for managing colors, so we'll change it like this:

// Change elements to red
el1.color = sf::Color::Red;
el2.color = sf::Color::Red;

// Change elements to white
el1.color = sf::Color::White;
el2.color = sf::Color::White;

As you can see, it's very simple, just change el1 and el2 to the actual elements that you're sorting.

Increment number of comparisons

Now, the last part, counting the number of comparisons.

Let's define an int variable just at the start of our function, and we'll increment it every time a comparison is made, and at the end of the function, return it.

Here is a pseudo-code example:

´´´ int myCoolAlgoritm(Vector& vector, int timeSleep) { int numComparisons;

for (sorting_conditions) {
	compare_elements;
	numComparisons++; // Increment value each comparison
}

return numComparisons } ´´´

Example

Let's see how our bubble sort function ends up!

int algo::bubbleSort(std::vector<Sortable>& sortElements, int timeSleep) {
	// This is the value that we increment and return
	int numOfComparisons = 0; 

	// Iterate through the vector
	for (int n = 0; n < sortElements.size() - 1; n++) {
		// If the actual element value is greater that the next one, swap the elements
		if (sortElements[n].value > sortElements[n + 1].value) {
			// Call swap function (the function manages swapping and color changing itself)
			algoUtils::swap(sortElements, timeSleep, sortElements[n], sortElements[n+1]);
		}

		// Incremenent number of comparisons each comparison
		numOfComparisons++;
	}

	// Return comparisons to be added to the comparisons made in the last loop
	return numOfComparisons;
}

And that's it! Your new and fresh algorithm should be up and running, I hope that this wasn't be too tidious to read, but I wanted to clarify everything 🧐!