Today, I’ll be continuing my posts related to different algorithms. I think sorting can be a bit intimidating at first but it learning how to sort correctly can help you in a multitude of ways. At one point or another, I’ve had to sort a collection of data in almost every web application I’ve built.
JS: Integer Reversal and Fizzbuzz!
JS: String Reversal, Palindromes, and Anagrams
BubbleSort
There are many ways to sort a collection of data and in this post, we’ll go over one of the easier implementations, BubbleSort.
Problem
Given a selection of data, return the sorted array.
bubbleSort([34, 62, -25, 12, 48, -81])// should return [-81, -25, 12, 34, 62]
Solution
To solve this using bubbleSort, we will be using a for loop within another for loop which gives us a time complexity of n² in case you were wondering.
Essentially, we will be looping over each number in the array and we will attempt to place the largest number at the very end of the array and repeating the process until each number is placed in the correct position.
let arr = [34, 62, -25, 12, 48, -81]In our array above, 62 would end up at the end after our first loop. We would then go through the first 5 integers in our array and then 48 would be placed just before 62. The next loop would then look at the first 4 integers and eventually place 34 before 48 and 62. I think you get the picture now.
Until you see this process in action, it may sound confusing. Let’s jump right into the solution.
We can start our solution by writing a basic for loop that will iterate over each integer in our arr array.
let arr = [34, 62, -25, 12, 48, -81]function bubbleSort(arr) { for (let i = 0;i < arr.length; i++){ }}
In past posts, I’ve been using for/of and for/in loops (which I love!) but in this case, a classic for loop is needed in order to get access to the index and each element. You will see why when we write out our second for loop that will be placed within our first for loop.
let arr = [34, 62, -25, 12, 48, -81]function bubbleSort(arr) { for (let i = 0;i < arr.length; i++){
for (let j = 0; j < (arr.length - i - 1);j++) {
/// logic goes here
}
}
}
We now have our outer for loop that will iterate over the entire array and our inner for loop. Our inner for loop will restrict the window over time and to do so we will always start at the index of 0 and subtract the length of arr by i and 1 ((arr.length — i — 1) ). Since we will be placing the largest numbers to the right through each iteration, it will no longer be necessary to include them in every subsequent for loop. Remember, the array length is always offset by 1 from the index since arrays are indexed by 0.
Now, we will place our code that takes care of the logic in the inner for loop. The logic will basically be a comparison between one element and the next. This is where all the magic happens!
let arr = [34, 62, -25, 12, 48, -81]function bubbleSort(arr) { for (let i = 0;i < arr.length; i++){
for (let j = 0; j < (arr.length - i - 1);j++) {
if (arr[j] > arr[j+1]) {
const smaller = arr[j+1];
arr[j+1] = arr[j]
arr[j] = smaller
}
}
}
}
What is going on in that conditional statement? We first look at the element in arr at index j and compare it to the very next element. If element arr[j] is greater than element arr[j + 1] , we want to swap them. If not, we leave it and move on to the next element.
How do we swap the element? To do that, we can create a temporary variable called smaller and assign it the number that is at index [j+1] . After that, the NEW value of arr[j + 1] will now be the greater number, arr[j] . The new number at the index of arr[j] is then assigned the value of the smaller variable and after that, the loop starts again but this time, we’d only be paying attention to the first 5 elements and ignoring the 62 that was placed at the end.
Let’s take a look at our array to see what happens to it after each subsequent loop so this can make a bit more sense.
//initial value of arr
[34, 62, -25, 12, 48, -81]//after firstloop
[34, -25, 12, 48, -81, 62]//after second loop
[34, -25, 12, -81, 48, 62]//after third
[-25, 12, -81, 34, 48, 62]//after fourth
[-25, -81, 12, 34, 48, 62]//after fifth
[-81, -25, 12, 34, 48, 62]
As you can see, after each loop, our “window” shrinks by one and we ignore the numbers that were placed at the end of the array! when our loops are done, we return arr and were done!
let arr = [34, 62, -25, 12, 48, -81]function bubbleSort(arr) {for (let i = 0;i < arr.length; i++){
for (let j = 0; j < (arr.length - i - 1);j++) {
if (arr[j] > arr[j+1]) {
const smaller = arr[j+1];
arr[j+1] = arr[j]
arr[j] = smaller
}
}
}
return arr;
}
That’s it! Hopefully, this made some sense to you. Next week, I will be going over another sorting algorithm that is a bit harder to grasp but because sorting is an important tool in every developer’s arsenal, it will still be just as important to learn.
Good luck and thank you for reading!
