Sorting Algorithms

Overview

Sorting algorithms are super cool. They are a good example of how there are many solutions to single problems, each with their own trade offs.

Sorting algorithms are algorithms for sorting collections of numbers: usually arrays. There are bunches of them out there, so I'm not going to over all of them, but I'll give you the five-cent tour.

They are usually measured using this thing called "Big O Notation" and/or "Omega Notation." There are a multitude of resources out there that can explain these much better than I currently can, so I'm going to leave them out of this article. Just know that there are metrics for measuring these algorithms.

I've written a few toy-examples of some sorting algorithms, you can find those here if you want.

Selection Sort

Selection sort is one of the more simple ones. Basically you start at the beginning, and scan to the end of the array and find the smallest item. Then you move it to the beginning. Then you repeat but starting at the second item and swapping the smallest one in the rest of the array with that. Then you repeat with the third, fourth, and so on.

Bubble Sort

I really like bubble sort. It's not necessarily the best or anything, I just think it's neat. Watching this one happen in a visualization does actually remind you of bubbles.

You take the first and second items in the array, and if needed swap them so that the bigger one is closer to the end of the array. Then you repeat this process using the second and third, third and fourth, and so on. You then do this again with the whole array (starting again with the first two items in the array) and again and again until no swaps are needed starting at the beginning and going to the end. The array is then sorted.

Heap Sort

Heap sort is super cool, but is also kind of harder to wrap your head around.

You first take your array, and create either a max or a min heap (using a max heap will leave the array sorted from least to greatest, while using a min heap will leave it sorted from greatest to least). You then move to root node to the end of the array, and treat it as no longer in the heap. You then make the rest of the array into the same type of heap as before and again move the root to the end (before the previous head though), again treating it as no longer in the heap. Repeat until sorted.

Conclusion

Sorting algorithms are a huge part of computer science. Some are good in some situations while others are better in other situations. These are just three but there are many many more out there, each one unique.