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;
}

Was this the shortest bubble sort?

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.