## DEV Community

Greg Bulmash 🥑

Posted on • Originally published at yiddish.ninja on

# JavaScript Bubble Sort in the fewest lines

I didn’t get my degree in CS, so every once in a while I’ll school myself in a CS concept. I’ve been asked about bubble sorts in interviews, so I decided to code one out in JavaScript.

## How does a bubble sort work?

Basically, a bubble sort function walks through an array, comparing each value to its right-hand neighbor and swapping them if the neighbor is smaller. It keeps walking through the array, over and over, until there’s nothing to swap.

It looks something like this.

``````Start: [9,6,3,2,4]
After 1: [6,3,2,4,9]
After 2: [3,2,4,6,9]
After 3: [2,3,4,6,9]
After 4: [2,3,4,6,9]
``````

Why did it go through four times when it had the correct order after the third?

Because it didn’t know the order was correct until it ran through it the 4th time and didn’t have to swap anything.

So I wrote a simple function.

``````function bubble(arr){
do {
var swaps = false;
arr.forEach((val, ind) => {
if (val > arr[ind + 1]) {
swaps = true;
arr[ind] = arr[ind + 1];
arr[ind + 1] = val;
}
});
} while (swaps == true);
return arr;
}
``````

It worked. But I wanted to make sure I’d written it in as few lines of code as I could. When I Googled “javascript most efficient bubble sort,” the top two results took 2-3 lines more to do it.

It came down to three things:

1. They were using `for` loops to iterate through the array while I was using `Array.prototype.forEach()`.

The `forEach` method provides the value of that element in the array, its index, and even the array itself to the callback function that operates on each element. So I saved a line of code.

When they needed to swap values, they had to declare a temporary value to hold one of them, but I already had one provided as an argument to the function.

My code getting the value and the index number (as `val` and `ind`):

``````if (val > arr[ind + 1]) {
swaps = true;
arr[ind] = arr[ind + 1];
arr[ind + 1] = val;
}
``````

Their code, only getting an index number (as `i`):

``````if (arr[i] > arr[i + 1]) {
swaps = true;
let temp = arr[i + 1];
arr[i + 1] = arr[i];
arr[i] = temp;
}
``````

2. They were also declaring a variable with the length of the array before creating their `for` loop, while `forEach` just sort of knows it.

3. One of them declared their `swaps` boolean outside the `do... while` loop with a `let` keyword. I and the other declared it inside the loop with `var`. The `let` keyword is block scoped, so if they declared the variable inside the loop, the loop controls couldn’t see it. The `var` keyword is function scoped so it could be seen anywhere in the loop after it was declared and assigned.

Using `let` didn’t significantly improve readability and added unnecessary complexity (in this case).

## Okay, it was shorter, but was mine better?

I was pretty pleased with myself, but I already knew of one trade-off of using `forEach`.

Once started, `forEach` has to complete the whole loop through the array. A `for` loop can use the `return` or `break` keywords to exit early, and it can use `continue` to end processing and skip to the next iteration. The `forEach` method doesn’t have any of those.

Where the `for` loop had an advantage was that the bubble sort has to iterate through all the values… almost.

It doesn’t have to compare the last value to the undefined value of the last index plus one.

A `for` loop can be set to iterate through all the values but the last, meaning one less run of the code in the loop.

Winner: `for` loop.

Another issue is the comparative efficiency of the two ways of determining the array length.

Internally, `forEach` is basically running a `for` loop and looking up the array length each iteration.

In the `for` loop variations, the array length was set once in a variable and then the loop used the variable.

If the array length might change during the loop, such as removing duplicates with a `Array.prototype.splice` method, looking it up on each iteration of the loop is very useful.

But where the size of the array is going to stay the same, getting the array length once and putting it in a variable for a `for` loop to use… depends on the engine, it seems. In V8 (Chrome, node.js), the lookup actually seems to be marginally faster (according to this Stack overflow discussion), but with other engines YMMV.

Winner: let’s call it a tie.

Last, on the `let` vs. `var` use, it’s really a question of whether declaring once + repeated assignment was faster than repeatedly declaring and assigning in one statement.

So I timed the two methods, running each 10 billion times in multiple tests. The `var` declaration and assignment method won by around 0.2% in each test. That’s not significant enough to call a winner.

Winner: let’s call that a tie too.

## So, was mine better?

Mine was shorter and more readable, but being able to skip an entire execution of the comparison code on each pass through the loop was a decided edge for the `for` loop. Therefore “better”… well, that depends on your priorities.

Greg Bulmash 🥑

While working on a selection sort (posting soon), I realized I could have used a destructuring assignment to cut two lines from the function.

Turn:
swaps = true;
arr[ind] = arr[ind + 1];
arr[ind + 1] = val;

Into:
[arr[ind], arr[ind + 1], swaps] = [arr[ind +1], arr[ind], true];

I think it would make it less readable, but it would definitely make it shorter.