I am a firm believer that the saying “fake it until you make it” is a complete bull*hit, especially in the field of computer science. Code is unforgiving. Period. One of the topics many programmers overlook and hate is studying classical algorithms and data structures. Yet, these fundamentals are still widely used in interviews especially for big tech companies and there is a good reason for that. Understanding what is happening under the hood and being able to reason which data structure is the right fit for a particular problem is an essential skill of a good programmer.
You might never implement a linked-list at work, yet knowing how to do it gives you a great base for solving real problems. Lastly, as coders, we should have a general knowledge of the underlying stones that shaped this industry to the point where we are now. Think of it as paying respect to the great minds that changed the way we live and work. Business students also need to know a thing or two about the work of Adam Smith or Karl Marx.
The need for sorting data is basically as old as modern computers. The analysis of the bubble-sort-like algorithm (the term used was “exchange sort”) was published back in 1956 by Edward Harry Friend. Yet, for instance, Radix Sort was defined even earlier back in 1887. Though, its memory-efficient version for computation was introduced in 1954 by MIT researcher Harold H. Seward.
Another well famous algorithm, that belongs to the group of fastest sorting algorithms still used is merge sort, invented by the legend himself John von Neumann back in 1945. Another O(log(n)*n) algorithm quick sort came to life in 1959.
A question that might be raised is if it’s needed to have dozens of algorithms for the same problem? Well, some algorithms are used for teaching purposes as they are easy to conceptualize, others perform better on specific sets of data, e.g. nearly sorted. Lastly, some are just faster than others applied to a randomized set of data.
Bubble sort is one of those “useless” algorithms for practical sorting. Why? It is slow (O(n*n)), even with an almost sorted array it will perform worse than insertion sort (coming soon), yet it is quite easy to implement and it is light conceptually, therefore a great place to start.
The premise behind bubble sort is comparing two adjacent elements in an array and swapping them in case they are not in order. Then repeating this process until the lowest element appears at the start of the array and the highest at the end. Simple enough? Let’s code it!
Selection sort is probably the most naive and intuitive solution for sorting. It also performs as bad as bubble sort (O(n*n)).
The idea behind selection sort is going through the array, finding the lowest element and placing it first, then repeating the process and finding the second-lowest element and inserting it as the second, and so on…
I decided to split the solution into three functions so it is more readable and conceptually easy to understand.
Last algorithm which belongs to the group of poorly performing ones, with one exception. It is quite good at sorting small almost sorted datasets. As we are gonna see with our better-performing algorithms, it is very hard to prevent them from doing extra work. Insertion Sort does the minimum sorting and can finish sooner.
Insertion sort is best explained with a metaphor of playing cards. Imagine the dealer is giving you a bunch of cards and you sort them in your hand as you are receiving them. That is basically the insertion sort -going through the array and we add each element to its right position, having the sorted “subarray” forming from left to right.
As the name suggests, quick sort is quick. Quicker than our previous three. Its time complexity is “only” O(n*log(n)) which is a vast improvement for large datasets. If we have 10 000 elements, we might go from roughly 100 000 000 operations to 137 000. This number is theoretical and the ratio will be way smaller if we measure by time… The important outcome is, that quick sort is generally way quicker.
Now, let's analyze how quick sort works. Firstly, we pick a pivoting element and divide the array into two subarrays of numbers smaller and higher than the pivot. So, we are using the divide and conquer strategy. That’s where the log(n) comes from. Then we perform this operation again using recursion on each of those arrays until we have arrays of zero or one element, those are by nature sorted. Then we just put all these numbers together in the right order.
It is important to mention, that the choice of the pivot can improve the time based on the dataset, it does not matter if we use a completely random number, but with almost sorted data it makes sense to start around the middle. For the sake of our implementation, we will pick the last element as the pivot as we don’t know anything about the state of the data we are getting and assume that they are randomized.
With merge sort, we simply split the array recursively until we have arrays of one element and then we always merge together subarrays starting from merging two arrays of one element, then two arrays of two elements until we merge together two arrays that are the original left and right “half” of the array.¨
Just take a pen and paper and try to go through the code writing down the values and visualizing the tree of calls in the case of recursion. Also, don’t worry if you don’t get a certain algorithm straight away, it is absolutely normal. Go through a bunch of articles and videos and it will eventually click.