Sorting Algorithms: Bubble Sort
What is bubble sort?
Bubble sort is a sorting algorithm; it sorts data by comparing two elements and swapping them based on values. I’ve come to see it as a starting point for understanding all other sorting algorithms. It’s something you are likely to run into in technical interviews and it makes for a great foundation before learning about other sorting algorithms. This blog post will go over what bubble sort is and how it works. I hope to make more posts in the future on other sorting algorithms.
Why is it called Bubble Sort?
The idea behind bubble sort is that if we are sorting an array from smallest to largest, the larger values will swap places with the smaller values, bubbling their way up to the end of the array. Or another way of thinking about it is, the larger values are sinking to the bottom.
What happens in a bubble sort?
• In a bubble sort, we loop through an array comparing two values.
• We then swap the two values so that the higher value is closer to the end of the array
• We continue comparing the higher value with other values along the array, swapping places if their is a higher value, until the highest value of the iteration reaches the end of the array
When we loop through an array we compare the two values next to each other, and we check, “is one larger than the other?”, and if it is, we swap the one that is larger, moving it closer to the end of the array. The largest values bubble to the “top” or the end of the array. And eventually we end up with a sorted array. Swapping is very important when we talk about sorting.
Before we sort we have to swap:
In this blog, I will show you two ways of swapping…
//FIRST
function swap(array, index1, index2){
let temporaryValue = array[index1];
array[index1] = array[index2];
array[index2] = temporaryValue
}
//SECOND
function swap(array, index1, index2){
[array[index1], array[index2]] = [array[index2], array[index1]]
}What is happening here? In both of the swap functions above, we pass in three arguments: the array, the index of the first object, and the index of the second object. Where the two differ is in the body of the function. In the first example, we are declaring a variable called “temporaryValue” that saves the position of index1 as its value. On the second line, we swap the position of the first value and replace it with the second value so now array[index1] = array[index2]. On the third line, we swap the position of the second value to equal the temporary value which is equal to what array[index1]’s original value at the start of the function. So now you have two new values for both array[index1] and array[index2] which were swapped from the original values.
BubbleSort Pseudocode
- First we Define a function called BubbleSort that takes in an array,
- Next we start looping from the start of the array towards the end with a variable called i = the length of the array(we are shrinking down the amount of space we are looping)
- Next start an inner loop with a variable called j from the beginning until j is equal to i-1 (i is referring to the i in the first loop)
- We will compare j to j+1 which is equal to the value in front of j. If array[j] is greater than array[j+1], swap those two values
- Then we return the output, which is the sorted array
function bubbleSort (array){
for (let i = array.length; i > 0; i--){
for(let j = 0; j < i-1; j++){
if (array[j] > array[j+1]){
[array[j], array[j+1]] = [array[j+1], array[j]]
}
}
}
return array;
}//EXAMPLE
bubbleSort([42, 50, 24, 15]);
// 42 > 50 ? False
// 50 > 24 ? True *swap* => 24, 50
// 50 > 15 ? True *swap* => 15, 50
// Next Run (i = 3)
// 42 > 24 ? True *swap* => 24, 42
// 42 > 15 ? True *swap* => 15, 42
// Next Run (i = 2)
// 24 > 15 ? True *swap* => 15, 24
// => [15, 24, 42, 45]
Finally to optimize Bubble Sort, we want to add one more thing. Let’s say we had a larger collection of data in the array, but reached a point where we are working with a collection of data that is nearly sorted. In the event that we did not sort on the last run of our loop, we want to just return the array. However with the way our function is set up, we will continue to loop through until j is equal to i-1. To add a break we can set a condition asking “did we swap on the last loop?” if we didn’t let’s just return the array. Because there is nothing left to sort.
function bubbleSort (array){
let noSwaps
for (let i = array.length; i > 0; i--){
noSwaps = true;
for(let j = 0; j < i-1; j++){
if (array[j] > array[j+1]){
[array[j], array[j+1]] = [array[j+1], array[j]]
noSwaps = false
}
}
if (noSwaps) break
}
return arr;
}bubbleSort([8, 4, 5, 6, 7])
// First Run (i = 5)
// noSwaps = True
// 8 > 4 ? True *swap* => 4, 8
// noSwaps = False
// 8 > 5 ? True *swap* => 5, 8
// 8 > 6 ? True *swap* => 6, 8
// 8 > 7 ? True *swap* => 7, 8
// noSwaps ? False
// Next Run (i = 4)
// noSwaps = True
// 4 > 5 ? False
// 5 > 6 ? False
// 6 > 7 ? False
// 7 > 8 ? False
// noSwaps ? True
// *break*
// => [4, 5, 6, 7, 8]
In the example above, we have a nearly sorted array, where the only value that needs to be sorted is in the 0 index of our array. When we run through the sorting algorithm a second time, nothing is sorted because all values are already sorted from least to greatest. Because nothing gets sorted on the second run of the bubble sort algorithm, when we hit our noSwap condition and it returns true, we break out of the loop and return the sorted array.
To recap, Bubble Sort is a sorting algorithm where on each run, we take the largest value and bubble it towards the end of the array, swapping it along the way with larger values if there are larger values. I hope this was helpful, I always learn so much from doing these blog posts. I look forward to writing more on the topic sorting in the future.
