Bubble Sort in Javascript

Bubble Sort is a common sorting algorithm that makes multiple passes of an array, each time moving the largest value left in the unsorted section the the end. It's called "bubble sort" because numbers bubble up to their correct position during each pass.

Bubble sort isn't the fastest algorithm, it takes on average/most n^2 time, and at a minimum n time. It is very space and memory efficient, only need constant space, and it does not use recursion.

It's important to visualize bubble sort first. We will walk through an example array with 5 numbers. We will highlight the number we are currently looking at in green, and use the double arrow to represent a value comparison. I've also added a partition that moves from the back of the array forward as we sort more elements.

To start, we look at the value 7 at the start of the array. We compare that with 3, and 7 is the higher value. We can swap the two values, and continue looking at 7.

We then can compare 7 with 1. 7 is greater than 1, so we swap values.

We repeat this process with 4, and then 5, until 7 has reached its rightful spot at the end of the array.

We return to the start of the array, where we can compare 3 with 1. 3 is moved to the second position.

3 is compared to 4, and this time, it does not change positions. Instead, we change our focus to 4.

4 is compared with 5. 4 stays in the same position, and we can move our partition up one spot. We can continue this process to finish sorting the array.

In order to sort the array, we needed to have two loops - one that move the partition forward, and one that makes a pass on the array. We can easily translate that to javascript, and write code in the second loop to swap values. I've written out a simple javascript version of bubbleSort below.

function bubbleSort(arr) {
    for(let i = arr.length - 1; i > 0; i--) {
        for(let j = 0; j <= i; j++) {
            if (arr[j] > arr[j+1]){
                let save = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = save
            }
        }
    }
    return arr
}