Bubble Sort

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)