One of the fundamentals of software development is algorithms. This is perhaps one of the scariest parts when you are starting out as a developer and is often neglected by those who have years of experience in the field.
Nowadays, algorithms are rarely used directly since many libraries provide implementations behind the scenes. But, it's important to learn about them, to at least know how to choose right algorithm for the right situation.
Perhaps the problem you have encountered has a solution that has already been studied, but not knowing the name or the type of algorithm that solves it, you end up implementing a solution that either is not the most optimal or simply does not work. That is why in this post, we are going to talk about the 5 most common types of algorithms that you should know and that you can find or need in almost any project.
We have all used the sort() function. This is included by default in nearly all languages, for example, to sort an array with a couple of values inside. The purpose of this feature is pretty simple if you have a set of data that are not sorted as for example:
[0, 23, 5, 91, 1]
The function will take care of sorting them as follows:
[0, 1, 5, 23, 91]
Or even in the reverse order, if you need it:
[91, 23, 5, 1, 0]
Simple, isn't it? However, behind the scenes, the operation is not so simple and can even be a bit hard, depending upon the algorithm you are using. Most likely, you are using some variant of the algorithms known as Quicksort or Merge Sort.
Its name is due to its ability to sort an array of elements significantly faster (two to three times faster) than any of the common sorting algorithms. But how does it work?
Quick sorting is a very efficient sorting algorithm that is based on partitioning an array of data into smaller arrays. A large array is divided into two arrays, one of which contains values smaller than the pivot value, based on which the partitioning is performed, and the other array contains values larger than the pivot value.
Quicksort splits an array and then calls itself twice to sort the two resulting arrays. This algorithm is quite efficient for large arrays, because of its medium complexity.
This is another algorithm that applies recursion and is based on the divide-and-conquer technique, dividing an array into several smaller arrays, until each of them has a single element, and then merging all those arrays so that a new ordered array is obtained.
Basically, it divides each set in half, and then each half is divided again by two, and so on until it cannot be divided any further:
[20, 11, 17, 7, 4, 0]
[20, 11, 17] [7, 4, 0]
[20, 11]  [7, 4] 
     
Now, the algorithm combines the elements following the same logic with which it divided them. It first compares the elements of each array and then combines them into another array, sorting the values. That’s why it has its own name.
[11, 20]  [4, 7] 
[11, 17, 20] [0, 4, 7]
[0, 4, 7, 11, 17, 20]
This is an algorithm to find a set of elements in an ordered array. The fact that it's sorted helps us find the elements faster without the need to run through the entire array. If you need to find one or several items within a sorted data array, you can use a library that implements this algorithm.
Like the previous algorithms, this one also follows the divide-and-conquer approach, where the array is divided into two halves and the item is compared with the central item in the array. If the match is found, the location or index of the center element is returned. Otherwise, either half is searched based on the result obtained by the match.
For example, let's look at this array of 8 elements in which we must search for the number 6:
[1, 2, 6, 9, 14, 16, 29, 30, 54, 60]
First, we must determine the middle with the following formula. Our references are the positions or indexes, not the values themselves (0–9).
low = 0
high = n - 1
mid = low + (high - low) / 2
low = 0
high = 9 - 1
mid = 0 + (8 - 0) / 2
mid = 4
Now we compare the value stored in position 4 with the value we are looking for, i.e., 6. We find that the value in position 4 is 14, which does not match. Since the value we are looking for is less than 14 and we have a sorted collection, we know that the value must be in the first half of the collection and we can discard the second half:
[1, 2, 6, 9, 14]
And so we apply the same formula again with our new collection with the following values:
low = 0
high = 3
This process should be repeated until low > high. If at some point we find that mid equals the value we are looking for, we return the value of that position. And if the value does not exist in the array, -1 is returned.
Graphs have been studied a lot and there are many libraries that implement them.
The two most widely used graph algorithms are BFS and DFS. These are widely used as the basis for many other graphs. These algorithms are basically able to tell you the distance of each node in the graph with respect to its origin, so they are widely used to find paths. In fact, they are the basis for the next algorithm, Dijkstra's algorithm.
This is an algorithm that if you have worked with GPS routes, surely you have heard of it or you have implemented it without knowing it. Dijkstra's algorithm is used to find paths in graphs, but it takes into consideration the cost of moving from node A to node B. That is, we can assign a cost or weight to each axis or each path, and with Dijkstra, we can find the path that minimizes that weight, i.e., the shortest path.
Based on the GPS example, we can have several routes, some longer than others. So, going through an avenue costs more than taking a shortcut through another street, so the vehicle or the user will be better off taking the shortest path.
And this brings us to the last family of algorithms that will surely be very useful:
An optimization algorithm seeks to either maximize or minimize some target value. For example, in the case of Dijkstra, we seek to minimize the cost of the path; we seek to find the path whose cost is lower. Also, in other types of problems, we can find the combination of items that maximizes a certain value.
There are many ways to perform optimization algorithms, among them implementing a brute force algorithm, which searches all possible solutions until it finds the best one. But this is not very efficient and can consume a lot of memory in a short time. Therefore, you have to find a way to do it a bit better, even if it implies perhaps the risk of not finding the best solution, but a moderately good one, thus minimizing the cost of the whole process. These implementations play with the theory of making the solution bit by b
For example, continuing with the graphs, we can add elements to the path and see what the cost is up to that point. That will give us a tree.
If we see these solutions being built and we know how to calculate their cost, it's easy to think that if we have two possible routes to take and one of them has a lower cost than the other, it's more likely that it's worthwhile to continue along with the one with the lower cost. Or if you see that your path already exceeds the target cost, maybe it's not worthwhile to continue that way.
As mentioned above, these systems are not perfect and cutting off a possible solution because it's worse at the time, i.e., its cost is high, does not mean that if it were completed it would not be the most optimal. These algorithms are mainly used to solve problems of great complexity that require expensive solutions that can only be obtained by brute force.
These are some of the families of algorithms that we should know about. So, if you face a problem of this kind, it's very possible that you can make better decisions if you know where to look and if you know which type of algorithm can help you.
We’d love to learn more about your project.
Engagements start at $75,000.