JavaScript Selection Sort

I had so much fun with the JavaScript bubble sort last night, I challenged myself to understand and code a selection sort tonight.

What is a selection sort?

A selection sort runs through an array once for each element. In each run, it finds the smallest value in the set of elements starting from that element through to the end of the array. At the end of that run, if that element isn’t the smallest, it swaps it with the one that is.

Let’s take a 4 element array, [8, 3, 1, 2].

For the first pass, we’ll create a variable n with a value of 0 to hold the array index of the smallest value in the pass.

First pass:

Compare 8 to 3, 3 wins and `n` = 1.  
Compare 3 to 1, 1 wins and `n` = 2.  
Compare 1 to 2, 1 wins and `n` remains 2.  
Swap the values at indexes 0 and 2, and the array is now `[1, 3, 8, 2]`.

We know the first item in the array is now the smallest, so we’ll start from the second and n starts at 1.

Second pass:

Compare 3 to 8, 3 wins and `n` remains 1.  
Compare 3 to 2, 2 wins and `n` = 3.  
Swap the values at indexes 1 and 3, and the array is now `[1,2,8,3]`.

Now we increase n to 2 and run again. This is actually the last pass we’ll need, because we’re comparing the last two values.

Third pass:

Compare 8 to 3, 3 wins, and `n` = 3.  
Swap the values at indexes 2 and 3, and the array is now `[1,2,3,8]`.

And we’re sorted.

A selection sort in JavaScript

Here’s the code.

function selsort(arr) { 
  var arlen = arr.length; 
  for (var i = 0; i < arlen - 1; i++) { 
    let lowest = i; 

    for (let n = i + 1; n < arlen; n++) { 
      if (arr[n] < arr[lowest]) lowest = n; 
    } 

    if (lowest !== i) {
      [arr[lowest], arr[i]] = [arr[i], arr[lowest]]; 
    } 
  } 
  return arr;
}

console.log(selsort([4, 15, 2, 9, 31, 3]));

And the console shows: [2, 3, 4, 9, 15, 31]

Couple of things to note.

In the outer loop (line 3), we only need to run it to the length of the array minus one. When we get to the second-to-last value, that comparison with the last value completes the sort.

Also, since we’re already setting the lowest variable to i (line 4), we start the inner loop (line 6) at i + 1, otherwise we’ll waste time on comparing index i to itself.

I’d read about destructuring assignment before, but if you don’t use it, you lose it. It fell out of my head like the subjunctive conjugations of “estar” from college Spanish.

I was sure there had to be a shorter way of swapping variables in an array than creating a temp variable then running two assignment operations, did some Googling, and destructuring was it (line 11). I could have saved two more lines in my bubble sort.

And there you go.