What is bubble sort
Bubble sort is a sorting algorithm. Sorting algorithms are used to sort data structures(typically arrays). Bubble sort
How it works
In bubble sort, we loop through each element in the array. In an inner loop, we compare the element to the next element. If the current element is greater, then we swap the elements
Step 1
Create a function that takes in an array. Make a for
loop that loops through the array.
function bubbleSort(array) {
for(let i = 0; i < array.length; i++) {
}
}
Step 2
Make an inner loop inside the first for
loop.
function bubbleSort(array) {
for(let i = 0; i < array.length; i++) {
for(let j = 0; j < array.length; j++) {
}
}
}
Step 3
Check if the current element is greater than the next one. If so we will swap them. To swap them, we create a temp
variable to store the current element. Then we set the value of the next element to the value of the current element. Finally we set the next element to the value of temp
which stored the first element.
function bubbleSort(array) {
for(let i = 0; i < array.length; i++) {
for(let j = 0; j < array.length; j++) {
if(array[j] > array[j + 1]) {
temp = array[j];
array[j] = array[j + 1]
array[j + 1] = temp
}
}
}
}
Step 4
Return the sorted array
function bubbleSort(array) {
for(let i = 0; i < array.length; i++) {
for(let j = 0; j < array.length; j++) {
if(array[j] > array[j + 1]) {
temp = array[j];
array[j] = array[j + 1]
array[j + 1] = temp
}
}
}
return array;
}
Refactoring and Optimising
This is fairly straightforward. If you look closely, we are still looping through the whole array even though as we progress throughout the loop, the elements at the end are already sorted. We can make our code much better with one simple refactor. In the first loop, instead of looping from the start, we can loop from the end. This avoids looping through the sorted elements at the end again.
for(let i = array.length; i > 0; i--) {
for(let j = 0; j < array.length; j++) {
if(array[j] > array[j + 1]) {
temp = array[j];
array[j] = array[j + 1]
array[j + 1] = temp
}
}
}
Another tweak we can make is that the inner loop should run as long as the āiā - 1 of the outer loop is greater than ājā of the inner loop. So, now the inner loop also excludes the sorted elements. We do the -1 to avoid counting the element being compared itself.
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]) {
temp = array[j];
array[j] = array[j + 1]
array[j + 1] = temp
}
}
}
}
Big O Notation
The Big O Notation of bubble sort is O(n raised to 2)
Top comments (0)