When talking sorting, and javascript there is a very real chance you have use the Javascript array.sort() method. Since it has a built in sorting method what is the point of learning others? Well after going over data structures it is safe to assume that you should not always be using arrays, and if you are I highly suggest at least learning some others. The problem with the default sorting method for javascript is that it sorts by comparing sequences of UTF-16 which [1,2,10,4,15] would return [1,10,15,2,4]. Keep in mind that it does provide a callback method in which you can tell it how you want to do the sorting (a-b, a.length - b.length, etc....), and with this callback method you can 100% get which results you need. But since we are on a journey of learning it's time to learn some other ways to manually sort data. We'll start with from what I've been told are the most basic and a lot of people consider them elementary algorithms but again knowing these other ways to solve problems is the first step in growing the knowledge that you'll need it the development career path. These three sorting algorithms are Bubble Sort, Selection Sort, and Insertion Sort.
Bubble sort by default is probably the most elementary sorting algorithm and probably the least efficient algorithm out there but it's also generally the first one that is taught because of how easy it is to visualize and understand. The way that bubble sort works is through two loops. You compare the first element of the array with the second element and if the first element is greater than (if you are sorting smallest to greatest), you would swap them. You continue this until you are at the end of the array. And with each iteration of the loop, 1 item is guaranteed to be "sorted". Please be aware that more can be however you will still need to loop over every index of the array. Once you do you will have a fully sorted array. Remember with each pass you make you loop through the length minus 1, as we know the final element is sorted each iteration.
Remember that loops within loops are extremely inefficient since their time complexities is factorial which is just about as worse as you can do. So if that is the case why even learn these elementary algorithms? Well first off it's good to have a knowledge of how to sort an array or structure if you need. So even being the most basic and horribly inefficient, it will still give you a solution to a problem. On a side note
The one use case in which Bubble Sort excels in is if you have an almost fully sorted array, and have one catch. Create a variable and during each pass set the variable to false. If a swap takes place make it true and at the end of the pass if it is false, return because we know we'd have a fully sorted array. Keep in mind you can set it to true to start call it something different and do the same if it is false. I don't have that coded in my files but feel free to add it in yours. Bubble Sort.
Selection sort is similar to bubble sort as its considered an elementary sorting algorithm, and as a high level overview what it does is the "reverse" of bubble sort (places high items sorted first), and it places smaller values in their sorted positions first. We are moving from the beginning to end but the sorted data is accumulated at the beginning instead of the end. We accomplish this by looping through the array and keeping track of the smallest value. After the first pass we swap the smallest value with the first position, and then on the second pass would be second position swap and so on and so forth. Remember for each pass we'll store the smallest value as the first item in that particular iteration.
As with Bubble Sort the time complexity in the worse case scenario is factorial which is extremely undesirable, again though when you are first starting out with any type of problem solving ( and this doesn't necessarily have to be related to development/programming ), getting to the finish line or a solution is the first step. If you cannot even finish a problem you don't really have room to say I don't need to know this since it's horribly inefficient. Horribly inefficient is still horrible but in the end it will give a solution so again, important enough to have an understanding of. Selection Sort
Insertion sort is definitely a little more complicated that Bubble and Selection. In an insertion sort we build up the sort by creating a larger left portion (of the array) which is always sorted. In this sorting algorithm we'll start with the second item in the array instead of the first and compare the two. If they need to be swapped we swap them otherwise we now move to the third position and then go back to the 2nd and 1st for comparisons. We insert the values if they are in the wrong position. So once we hit the last item in the array and then it goes down the array and it is either inserted or left alone, we'll have a fully sorted array. Insertion Sort.
Top comments (0)