Sometimes, for fun, I like to give myself small leetcode-like questions in the morning and see if I can have an answer by the end of the day. This is a fun way to keep my skills sharp and learn new concepts. Today's task started simple enough.
Given an array of numbers not in numerical order, sort the array so that its contents are in numerical order(lowest to highest)
I made a mess
First I tried something using deeply nested for loops that became an unreadable mess before it became functional. Then I tried an approach that added all the numbers together, got the median then tried sorting based if higher or lower. This also didn't work. So I googled it to see what others have done. This is how I stumbled upon the bubble sorting algorithm. My final result now looks like this.
let arr = [10, 21, 3, 45, 15]
let test = function(arg){
let bul;
do{
bul = false
for(let i = 0; i < arg.length; i++){
if(arg[i] > arg[i + 1]){
let temp = arg[i]
arg[i] = arg[i + 1]
arg[i + 1] = temp
bul = true
}
}
}while(bul)
return arg
}
console.log(test(arr))
why does this work
The basics of this algorithm is to take the first element and compare if it is larger than the next element. If it is, swap them, then repeat until we have made a full loop of the array with no changes. That's it, just some simple math and conditionals.
how does this work
We use a variable bul
that is a bullion to let us know if there have been any changes on this iteration. Declaring this variable is the only statement outside of the do/while loop. This loop is set up so that as long as the variable bul
remains true we will execute the contained function. This function contains a For
loop that iterates over the array. We then use an if statement to see if the current element is larger than the next element. If it is, we create a variable temp
to store the current element. Change the current element’s value so that it is equal to the next element (if the second element was 2 now both the first and second element are 2). Then we use our variable to copy the value that was our current element into the next element. At the end of all this we change the variable bul
to true, This is what keeps the loop going. Once the if statement is not triggered it means we have looped over the whole array without making any changes, meaning all values are where we want them.
when to do this
If you understand big O notation (an equation often used to measure the efficiency of algorithms in computer science) bubble sort is O(n^2). This is not great in terms of efficiency but let's talk about why. Since the algorithm is nested loops and we are making comparisons between different elements, the time it could take to complete is the square of the number of inputs. In Fact each time you nest another loop you would add another power to n. So nesting one more for loop would make the efficiency O(n^3).
Big O notation aside the long and short of this is The more you have to sort the longer it takes to sort it. Bubble sort is a great and simple algorithm but for large data sets is impractically slow for most use cases. If your array is a few hundred elements, bubble sort is probably a great fit. Thanks for joining me in learning about bubble sort, I hope this has helped you in some way.
Top comments (1)
Thanks a lot for this.
I have also seen this short example of doing this.
Thanks