It is quite common in Software Engineering interviews to be asked to code up a popular sort or search algorithm. Below is one approach to build-up the Bubble sort algorithm in JavaScript.

Since Bubble sort requires swapping array elements, we will need a utility function that allows us to swap elements at their respective indices within a given array.

``````function swap (array, firstIndex, secondIndex) {
var tmp = array[firstIndex];

array[firstIndex] = array[secondIndex];
array[secondIndex] = tmp;
return array;
}``````

To accomplish this, we use a variable to temporarily hold the value of the first element, then push the second element into the spot of the first, and finally take the value from the `tmp` variable into the spot of the second index in the array.

With that, we can take the first stab at putting together the actual sorting algorithm. Bubble sort works by moving through the array from left to right, comparing adjacent elements. It performs a swap between the two if the value of the left (the one with the lower index) is greater than the one on the right. The sort is complete if, after the last pass, no more swaps need to be made.

Lets focus first on the initial loop necessary to examine array elements that are next to each other.

``````var array = [ 1, 4, 3, 2 ];
var lastIndex = array.length - 1;

// look through the array between 0 and lastIndex
for (var i = 0; i < lastIndex; i++) {
// if the current item is greater than
// the next item, swap them
if (array[i] > array[i + 1]) {
array = swap(array, i, i + 1);
}
}``````

This will perform one pass through the array, swapping 4 with 3 and, subsequently, 4 with 2, leading to `[ 1, 3, 2, 4 ]`. 4 has moved to its correct location, however, we will need one more run through the array to get 3 and 2 swapped to achieve the correct result. Let’s remember that we know we are done sorting if, after a loop through the array, there were no more swaps necessary. We can make use of that by using another, outer loop whose test condition is based on whether any swapping occurred in the previous run.

``````do {
// we start off with the assumption that the array is already sorted
swapped = false;

for (var i = 0; i < lastIndex; i++) {
if (array[i] > array[i + 1]) {
array = swap(array, i, i + 1);
// a swap has occurred, we need to do another pass through the array
swapped = true;
}
}

// after each for-loop, the last item in the array is in the correct place
// move on to next loop, examining from the start of the array to the next
// to last item
lastIndex--;
} while (swapped);``````

In the above example, after the first pass we would end up with `[ 1, 3, 2, 4 ]`. The swapped variable would be `true`, so we would go through the array again. The algorithm would swap 3 and 2, leading to `[ 1, 2, 3, 4 ]`.

The array is now sorted correctly, however, the algorithm itself is not aware of that fact. It knows that another swap has occurred in the previous run, so it needs to walk through the array again. This time, the condition of the if-statement is never met, `swapped` remains `false` and we exit the while loop. We can now encapsulate this logic into a proper function, which you can find below, including the `swap` helper function, using ES6 syntax.

``````/**
* Swaps two items within a given array
*
* @param {Array} array array to be processed
* @param {Int}   firstIndex index of first item
* @param {Int}   secondIndex index of second item
*
* @returns {Array}
*/
const swap = (array, firstIndex, secondIndex) => {
const tmp = array[firstIndex];

console.log('[swap] Swapping ' + array[firstIndex] + ' with ' + array[secondIndex]);

array[firstIndex] = array[secondIndex];
array[secondIndex] = tmp;

return array;
}

/**
* Bubble Sort Algorithm
*
* @param {Array} array array that should get sorted
*
* @returns {Array} sorted array
*/
const bubbleSort = (array) => {
let lastIndex = array.length - 1,
swapped;

do {
swapped = false;

// look through the array between 0 and lastIndex
for (var i = 0; i < lastIndex; i++) { // if the current item is greater than the next item // swap them if (array[i] > array[i + 1]){
console.log(array);
array = swap(array, i, i + 1);
swapped = true;
}
}

// after each for-loop, the last item in the array is in the correct place
// move on to next loop, examining from the start of the array to the next
// to last item
lastIndex--;
} while (swapped);

return array;
}
``````

If we run this using Node, the output in the terminal is as follows:

``````\$ node bubble_sort.js
[ 1, 4, 3, 2 ] [swap] Swapping 4 with 3
[ 1, 3, 4, 2 ] [swap] Swapping 4 with 2
[ 1, 3, 2, 4 ] [swap] Swapping 3 with 2
Final: 1,2,3,4``````