Al Gore — Rhythm? Let’s sort this out.
Okay. Bad title. I tried finding a gif of Al Gore dancing and the conclusion I came up with is that he doesn’t dance.
Many of us go through the day and without thinking, sort all sorts of things. You notice your pajamas in the bathroom? Put it back in the drawer where it belongs. Color pencils not in the right order to display a beautiful rainbow? Work on it and make your life happier. Money in your wallet out of order after a good night out? Fight the hangover and arrange it. An M&M in a skittles pile? That’s a felony.
The point is, it’s easy for us humans to sort things out because it is natural. We don’t think about it for too long. When was the last time you looked at a single sock and couldn’t figure out which unlucky sock was missing its S.O.? Bad example — too many single socks out there, but you get the point. Let’s talk about computers. What does a computer do?
Exactly what you tell it to do. When you’re solving a problem regarding sorting, the computer is limited to your thinking, but because you can’t emulate your way of thinking in a computer’s language, it can be tough. We’ll go over some sorting algorithms.
Insertion sort works by taking elements from the list one by one and inserting them in their correct positions into a new sorted list. It’s efficient for small lists, but it’s expensive because it requires the shifting of all elements one by one, repeatedly.
Selection Sort works by iterating through the array and finding the lowest number. After the lowest number is found, it is swapped to the beginning of the array and moves on to the next index. That index is then set as the lowest number until a lower number is found which is then swapped with that current index. This is efficient for small lists as well but also expensive as it requires iterating through the array multiple times with each element.
Merge Sort is a divide and conquer type of algorithm. It takes an array and divides the length of the array by two. It then takes the arrays and splits each of them into two again. It continues to do that until there is just one element left in each array. After doing so, it starts to merge arrays, two at a time, while sorting them. It ends once there is one array that contains the original number of elements in the first array. This sorting algorithm is able to scale to larger lists, but you can see how it can be inefficient when some elements in the array are already sorted.
Heap Sort is considered a more efficient sort than selection sort. It works by placing the highest number at the back end of the array and shrinking down the size of the array it works on. It accomplishes this by using a special type of binary tree, called a heap. Once the heap is made, the root node is guaranteed to be the highest number and as the array is rearranged, the highest number is removed from the heap and continues this process.
Quick Sort works by selecting an element in the array and making it the pivot point. It compares all the elements in the array and creates two subsets of the array, one being all elements that are lower than the pivot point (and all the numbers are moved to that side) and the other being higher. The pivot point then moves to the middle of the array and it repeats the same concept with the left side of the pivot point. It continues to go through the array until it is sorted.
Bubble Sort and Variants
Bubble Sort is a simple yet inefficient algorithm when it comes to sorting. It goes through the array starting at the beginning and compares the first two elements. It swaps the elements if the first element is greater than the second and then moves on to elements number two and three. From there, it’s an iterative process (i.e. compares and sorts then moves on to three and four, etc.) until it reaches the end of the array and then starts from the beginning again. The entire process stops when the algorithm goes through the array with no swapping taking place. This algorithm isn’t used very commonly in practice due to its inefficiency.
Comb Sort is similar to bubble sort, but is a bit more efficient. The way this algorithm works is by having a large gap factor and shrinking down in size through each pass of the array. In a bubble sort, the elements being compared are right next to each other so the gap factor is 1. In contrast, in the comb sort, we start with a larger gap size and shrink it down with a gap shrink factor. Through each pass, the array will be sorted (with the last pass being a bubble sort).
There are a few more sorting algorithms, but we can explore them later. These are the main algorithms that are discussed. If you look more into each algorithm, you can explore their BigO notations and see what might be the best algorithm to use in your case.