Comprehending the nuts and bolts of sorting algorithms can be daunting. But, getting comfortable talking about some of the well-known algorithms may help you ace a programming interview. So, without further ado, let’s dive right in.
First, a broad question. What exactly is the purpose of a sorting algorithm? In case the name sorting wasn’t indicative enough, it is the job of a sorting algorithm to take an unordered list of numbers and, well, order them.
#pre-sorted numbers = [5, 1, 4, 2, 3]#post-sorted numbers = [1, 2, 3, 4, 5]
Sorting an unordered list of numbers greatly increases the power you have over those numbers. Sorted lists allow you to better pick apart the information hiding inside the numbers.
But, before jumping into the details of each sorting algorithm, I’d like to lay the foundation for some terminology that will be discussed (notably Big-O), as well as the structure I’ll be using to review each algorithm.
If this knowledge is already in your wheelhouse, skip further ahead.
If you were to look up information on sorting algorithms, there’s a good chance you’ll run into talk of Big-O.
Sounds like a bouncer at the mathematics bar. “Wassup Big-O.”
So who or what is Big-O?
A function’s Big-O Notation spells out how the running time (also known as time complexity) is affected by the amount of data present in the list. The more data you have, the longer the sorting algorithm will take to sort the data. One algorithm may take longer than another to sort the same list of numbers.
Take, for example, O(n²) vs O(n log n) as shown in the graph above. As the amount of data (n) increases, you would much rather use an algorithm with a Big-O of (n log n) as opposed to (n²) because it will operate much faster. Think about having datasets in the amounts of millions or billions. Each tiny increase in run time adds up quickly, and you could cripple your computer’s memory and processing power for the duration of the sorting algorithm.
Senior developers and data analysts are always looking for the best algorithm to fit the needs of the dataset. Generally, an algorithm that sorts quickly and efficiently will be used.
It is because of this that Big-O becomes of the utmost importance when selecting a sorting algorithm to use.
I’ll also be using the terms stable and unstable with reference to the sorting algorithms.
A stable algorithm leaves the ‘like’ elements in the same order in the output array as they came in from the input array. As opposed to unstable, where the algorithm may mix ‘like’ elements. This is generally a non-issue, however it may be important for an algorithm to be stable, depending on the use of the sorted data set.
And finally, the algorithms have arrived.
I’m going to take a look at six sorting algorithms that are widely spoken of. They are:
- Bubble sort
- Selection sort
- Insertion sort
- Merge sort
- Quicksort
- Heap sort
For each algorithm, I’m going to translate the basics of what the algorithm is doing, take a look at the Big-O notation for the algorithm and address some of the strengths and weaknesses of the algorithm.
I start with the three more simple sorting algorithms (bubble, selection, & insertion) and then move on to the others. The simple sorting algorithms are notably more easy to understand and implement, but are generally slower than the other three.
Let’s take a look at the first one of the list: Bubble Sort
So how does it work?
Bubble sort cycles through the array of numbers, and looks at each pair of adjacent numbers. Bubble sort will then place the lower number on the left, towards the beginning of the array, and the higher number on the right, towards the end. This process is repeated and bubble sort will continue to loop through the array until no swaps are made, thus leaving a sorted array.
Let me stress, bubble sort is slow. With a worst-case time complexity of O(n²), bubble sort is not a very effective sorting algorithm, nor one that is used today.
That being said, bubble sort could be potentially useful for lists that are already sorted and only a small handful of swaps need to be made. Also, bubble sort is what’s known as an in-place algorithm so it doesn’t use a whole lot of extra auxiliary processing power from your computer.
Still, the weaknesses greatly outweigh the slim benefits and there are other simple algorithms that perform the same sorting features as bubble sort but are better at it. Such as —
Selection Sort
Selection sort works by splitting the input array into two parts: the list of numbers being built, from smallest to largest, and the remainder numbers that have yet to be sorted. Selection sort finds the smallest number from the unsorted list, and places it at the end of the sorted one. Rinse and repeat.
With a big O notation of O(n²), selection sort is another algorithm that is not very effective for sorting large arrays. While slightly outperforming bubble sort when working with small lists, selection sort is still viewed as a very slow algorithm.
And, sadly, selection sort doesn’t have a whole lot going for it. Instead, the most commonly used of the simple sorting algorithms is —
Insertion Sort
Insertion sort is similar to the previous two algorithms in that it’s big O notation is also quadratic, O(n²). Insertion sort works by building the final, sorted array one item at a time. The algorithm will iterate through the initial array, remove one element, and place it in its proper place as a part of the sorted list.
Insertion sort is generally the most used of the simple sorting algorithms for its plethora of strengths. Including, but not limited to:
- Adaptive — efficiently sorts data that is already generally sorted
- Stable — does not change the order of ‘like’ elements in the array
- Online — can sort the array as it receives new items
- In-place — requires a consistent, small amount of memory to run
- Simple Implementation — not a lot of code needed for the algorithm
For small lists (small is a relative term, but really anything less than or around 1,000 items) you simply can’t go wrong with insertion sort. It has all the benefits of the previous two basic sorting algorithms while also adding in its own strengths.
If time and space are limited and you don’t anticipate a large or increasing list of numbers, then check out cha-boy, insertion sort
On to the more advanced, and more commonly used, sorting algorithms.
The following three algorithms excel where the previous three did not: sorting large lists efficiently. We’re talking big data, hundreds of thousands, millions, or billions of items.
I’m only digging into the basics of the algorithms, but the customization typically used beyond the basics for each algorithm is staggering. We’re talking size-able amounts of complicated code.
But, I digress, let’s stick to the basics for now.
First of the bunch: Merge Sort
Merge sort operates by first breaking an array into its individual components. It then ‘pairs up’ an individual with another, putting them into their proper place (sorted) with reference to each other. Merge sort then continues to pair up each sublist of numbers and sort them in the process. This is continued until there is just one list remaining — the sorted array.
Merge sort is a powerful sorting algorithm. With a worst-case performance of O(n log n), it is significantly faster at sorting larger amounts of data than the previous, simple, sorting algorithms.
Merge sort is what’s known as a divide and conquer algorithm, which is pretty self explanatory. It divides up the dataset and conquers in groups, instead of one number at a time. Merge sort is also a stable sorting algorithm, which is yet another tool in its toolbelt.
However, merge sort does require a scaling amount of auxiliary processing power to work. Gotta give the guy some space. That being said, this algorithm blows the other, simple, algorithms out of the water, especially when working with large data sets. So keep your eye on this one.
Now for the Tasmanian devil:
Quicksort (ironically named because it’s really not even the fastest)
Developed initially in 1959, quicksort is another powerful sorting algorithm that is still used frequently to this day.
Quicksort is one of the more confusing algorithms to understand, so buckle up.
Quicksort works by:
- First selecting a pivot number in the array,
- Then sorting the other numbers by placing them before or after the pivot number respectively.
- At this point, the pivot number is in the correct location, and the two groups of numbers (one on each side of the pivot number) still need to be sorted.
- New pivot numbers are then chosen within the remaining subsets, and this process is repeated until no swaps are made.
Worst-case time complexity for quicksort is O(n²), although this is an algorithm that rarely falls into its worst-case performance, especially with minor amounts of customization. Typically the Big-O for quicksort is O(n log n). However, a worst case of O(n²) is a knock against it.
Quicksort is effective for its speed and small amounts of additional memory needed. However in its base form, is an unstable sorting algorithm.
As always, the pros need to be weighed against the cons, and the algorithm need be implemented at the proper place and time. Quicksort can be fast and highly efficient, given the right circumstances.
Lastly, Heapsort
Heapsort’s algorithm is… meaty to say the least. I’m going to keep the details down to a minimum but if you’re curious, there are many resources you can find online that go into further detail about heapsort and the binary tree.
Heapsort is, at its core, an upgraded version of selection sort. They are similar because heapsort breaks down the input data into two groups, sorted and unsorted, and builds the sorted group one number at a time.
Where they differ, is where heapsort uses, a heap, to build the unsorted group so its not blindly finding each number, one at a time. Heapsort adds the largest number from the unsorted group to the sorted group, then rebuilds the heap and repeats the process, adding the highest number to the sorted group.
That’s putting things simply, but it’s the gist of how heapsort works.
*For more information about the heap, check out the links above. Be warned, like an old ex, it’s complicated.*
Heapsort is yet another powerful worst-case O(n log n) algorithm. Meaning, at worst, it still outperforms all the simple algorithms and quicksort. That being said, heapsort is not a stable sort so choose wisely.
Heapsort also uses a fixed amount of auxiliary space to do the sorting, which is a big plus. Merge sort on the, on the other hand, uses more auxiliary space when there is more data.
The three advanced algorithms are the ones most commonly used in this day and age. They each have their own strengths and weaknesses, and data analysts need to the choose which is best for any given situation.
*long-winded exhale of breath*
Digesting even the basic details of these sorting algorithms isn’t something that’s easy to do in one read-through. If this is interesting to you, I highly suggest watching some videos or using some of the many interactive, online tools available to hone your understanding.
As I said at the beginning, having conversational knowledge about sorting algorithms will help you answer questions about Big-O and the like in a technical interview.
So… *as mentioned in Finding Nemo* just keep sorting
