sorting Algorithms are very essential in any programming languages, some are inbuilt so you don’t have to worry yourself using them, the case like JavaScript you can just use data.sort() to get a result. so then why the hell do you need to know how the sorting actually works if you have them inbuilt into JavaScript ? Well if you run the above method on a string data you might be happy with your result or your output but don’t cry if you get a different result when performing the same function on numbers, the method considers the number’s character codes instead of the numbers itself which accounts for the sorting done in non human understanding. to fix this or get your own expected results either you provide some parameters to the sorting method to get you the expected results or build your own algorithm for sorting which is what we’re going to do. So we have different types of sorting Algorithms but we will start with Bubble sort.
Bubble sort
Bubble sort is a sorting algorithm that has a rule of sorting by using two adjacent elements for comparism and adjusting them according to their order of sort. this means your bubble sort function should be able to take two elements close to each other and check if the first is greater or smaller than the second and if so then either swap them or remain in-place based on the order of sorting them.
I made mention of swapping and from now on this is going to be one of the common functions or procedures you might probably have to memorize or understand in order to do well in most of the sorting algorithms because they will be involved a lot of times since this is a matter of changing positions of items in a given collection.
let have a look at how swapping is done in two ways using a temp variable or the new ES6 syntax which in my opinion is the easiest and shortest.
Option 1 with Temp Variable
function swap(arr){
let temp = arr[0];
arr[0]=arr[1]
arr[1]=temp;
return arr;
}
console.log(swap([4,5]));//[5,4]
Above we have an array that consist of two elements which we need to be swapped over each other, we create a temp variable to hold the value of one and equate it to each order then replace their values with temp. try understand this concept by looking at the above code. let’s take a look at another version which is from the ES6 standard
function swap(arr, idx1, idx2){
return ([arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]);
}
console.log(swap([4,5,8,6,7,3],2,5));//[3,8]
this is no different from the above but here I tune the pattern a bit to make you understand you might have it in different flavor. looking at the above solution notice in this case we provided an array and specified the index of the two values to be swapped. ie. index 2 & index 5 which are 8 and 3 respectively resulting into [3,8] obviously.
now that we have a way to swap now let’s pass to how to best implement a bubble sort Algorithm.
function bubbleSort(arr){
for(i=arr.length;i>0;i--){
let swaped=true;
for(j=0; j<arr.length;j++){ if(arr[j] > arr[j+1]){
[ arr[j],arr[j+1] ] = [ arr[j+1],arr[j] ]
swaped=false;
}
}
if(swaped===false) break;
}
return arr;
}
bubbleSort([8,1,2,3,4,5,6,7]);
console.log(swap([4,5,8,6,7,3],2,5));//[3,8]
This is a very optimized version of the solution. this is so because here we check if the element has been swapped already, if so and the elements are sorted then there is no need to continue checking but rather end the program making it very fast to get result. Bubble sort in it unoptimized version has a worse case scenario of O(n²) Time Complexity but with an already partially sorted data the Algorithm will be much faster which results into a best case scenario of O(n) Time Complexity in rare cases. Bubble sort is a very stable algorithm with a space complexity of O(1) because no new variable is created except to check for if the elements have been swapped already.
let’s take time to digest the information above until the next post. Stay safe