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, const std::atomic<bool>& interrupt); // Our new algorithm
}

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

int algo::bubbleSort(std::vector<Sortable>& sortElements, int timeSleep, const std::atomic<bool>& interrupt) {
        // Let's return 0 for now.
	return 0;
}

As you can see, every algorithm function takes 3 parameters:

• Reference to the sorting vector
• Time to wait between each iteration
• Boolean used to stop the algorithm, if it's set to true, the function should return.

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

Go to SortController.cpp and locate _startSort(). This function contains a loop that will run calling the algorithm function selected until the vector is sorted. Let's add a new switch case!

void SortController::_startSort(int sortType) {
	...
        switch (sortType) {
		...
		// Our new case, use the next sortType available
		case 17:
			numOfComparisons += algo::bubbleSort(_sortElements, _timeSleep, _interrupt); // Our new algorithm
			break;
		default:
			return;
	}
        ...
}

As you can see, we add the function return to numOfComparisons. This variable will save the number of comparisons that our 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 translates the sortType number, the same that we defined before in the switch case, into a string redable by the user selecting the sort type. Add a new switch case like you did before with the same number!

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

	default:
		return kNoSort;
	}
}

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.- Adding functionality

Let's go to the function that we defined in SortAlgorithms.cpp, here we'll define the sorting algorithm functionality, let's see an example of a bubble sort algorithm:

int algo::bubbleSort(std::vector<Sortable>& sortElements, int timeSleep, const std::atomic<bool>& interrupt) {
	int numOfComparisons = 0;

	for (int n = 0; n < sortElements.size() - 1; n++) {
		if (interrupt) {
			return numOfComparisons;
		}

		if (sortElements[n].value > sortElements[n + 1].value) {
			algoUtils::swap(sortElements, timeSleep, sortElements[n], sortElements[n+1]);
		}
		numOfComparisons++;
	}

	return numOfComparisons;
}

You don't need to understand what the algorithm is actually doing to sort the vector in this case, don't worry!

Before explaining anything else, you should know that every algorithm function is being called in a loop that will run until the array is sorted, so you don't need to check if it's sorted before returning the function.

Things to know

• Every algorithm should return an int containing the number of comparisons made, in this case we're defining numOfComparisons, incrementing it while sorting, and returning it at the end of the function. Our bubble sort compares the elements in a for loop, so every for iteration we're incrementing it.

• Observe that we're checking every iteration if interrupt is true, in that case we'll return the current number of comparisons made at this point, the program will manage everything else.

• If you need swap elements in your algorithm, there is a function made for that called algoUtils::swap(). This will swap the elements, add the timeSleep delay, and change the colors, so you don't need to worry!

If you don't want or need to use algoUtils::swap() you can do it manually yourself, just know that sfml uses it's own types for colors. See how algoUtils::swap() manages colors and time sleep (it's so simple)!