In this first post of the Computer Science in JavaScript series, we're going to look at one sorting algorithm called Selection Sort. We'll look at two variations of this algorithm.

How Does Selection Sort Work?

Imagine you have an array of songs that you want to sort by the number listens.

let songs = [
  { title: 'The Bad Touch', listens: 55 },
  { title: 'Alone', listens: 71 },
  { title: 'Warm Machine', listens: 45 },
  { title: 'Daylight', listens: 85 },
  { title: 'Shadows', listens: 13 },
];

If we want to sort the songs in descending order by listens, one approach is to go through the array once and find the song with the highest number of listens. We'll put that song at the bottom of another array called sortedSongs and remove it from the songs array. We'll have something like this now:

let songs = [
  { title: 'The Bad Touch', listens: 55 },
  { title: 'Alone', listens: 71 },
  { title: 'Warm Machine', listens: 45 },
  { title: 'Shadows', listens: 13 },
];

let sortedSongs = [{ title: 'Daylight', listens: 85 }];

Then we'll do it again. This time, the "Alone" song has the highest number of listens in the songs array so it will be removed from songs and placed at the bottom of sortedSongs:

let songs = [
  { title: 'The Bad Touch', listens: 55 },
  { title: 'Warm Machine', listens: 45 },
  { title: 'Shadows', listens: 13 },
];

let sortedSongs = [
  { title: 'Daylight', listens: 85 },
  { title: 'Alone', listens: 71 },
];

We'll do this again and again, until there are no more songs left in the songs array. That is Selection Sort!

Let's look at how to implement this algorithm in JavaScript.

An Implementation in JavaScript

Here is an implementation of Selection Sort in JavaScript with comments:

function sortSongs(songs) {
  let sorted = [];
  let total = songs.length;

  while (sorted.length < total) {
    // find the index of the song with the most listens
    let highestIndex = 0;
    songs.forEach(function (song, index) {
      if (song.listens > songs[highestIndex].listens) {
        highestIndex = index;
      }
    });

    // move the song with the most listens from
    // the songs array to the new sorted array
    sorted.push(songs[highestIndex]);
    songs.splice(highestIndex, 1);
  }

  return sorted;
}

See this in action on JSBin

One downside to this implementation is that we are modifying the songs array. If you run console.log(songs), you'll notice that it is now empty. That is because Array.prototype.slice is mutating, which means that it modifies the array. If you didn't want this side effect, we can modify our code so that we create a new array from the songs array before doing the selection sort. It is just one line of code added:

function sortSongs(songs) {
  // create a new array from the songs array so
  // the original songs array isn't modified
  songs = songs.concat([]);

  // everything else is the same
  let sorted = [];
  let total = songs.length;

  while (sorted.length < total) {
    let highestIndex = 0;
    songs.forEach(function (song, index) {
      if (song.listens > songs[highestIndex].listens) {
        highestIndex = index;
      }
    });

    sorted.push(songs[highestIndex]);
    songs.splice(highestIndex, 1);
  }

  return sorted;
}

Try it out in JSBin

A Variation of Selection Sort with Swapping

Another way to approach this algorithm that you'll often see is with swapping.

Let's start off with our list of songs again:

let songs = [
  { title: 'The Bad Touch', listens: 55 },
  { title: 'Alone', listens: 71 },
  { title: 'Warm Machine', listens: 45 },
  { title: 'Daylight', listens: 85 },
  { title: 'Shadows', listens: 13 },
];

We'll iterate over the list of songs starting at index 1 and compare songs[1].listens with songs[0].listens. If songs[1].listens is less than songs[0].listens, we'll swap the two positions. Let's go through it.

Now the list looks like this:

let songs = [
  { title: 'Warm Machine', listens: 45 },
  { title: 'Alone', listens: 71 },
  { title: 'The Bad Touch', listens: 55 },
  { title: 'Daylight', listens: 85 },
  { title: 'Shadows', listens: 13 },
];

After a first pass, songs will now look like this:

let songs = [
  { title: 'Shadows', listens: 13 },
  { title: 'Alone', listens: 71 },
  { title: 'The Bad Touch', listens: 55 },
  { title: 'Daylight', listens: 85 },
  { title: 'Warm Machine', listens: 45 },
];

We'll do it again, but this time compare songs[1] with the rest of the songs in the list.

Now songs will look like this:

let songs = [
  { title: 'Shadows', listens: 13 },
  { title: 'The Bad Touch', listens: 55 },
  { title: 'Alone', listens: 71 },
  { title: 'Daylight', listens: 85 },
  { title: 'Warm Machine', listens: 45 },
];

After a second pass, songs will now look like this:

let songs = [
  { title: 'Shadows', listens: 13 },
  { title: 'Warm Machine', listens: 45 },
  { title: 'Alone', listens: 71 },
  { title: 'Daylight', listens: 85 },
  { title: 'The Bad Touch', listens: 55 },
];

We'll keep doing this until we've reached the end of the list, which at that point the songs array will be sorted by listens in ascending order.

Here is an implementation in JavaScript:

function sortSongs(songs) {
  let indexToCompare = 0;
  while (indexToCompare < songs.length) {
    for (let i = indexToCompare + 1; i < songs.length; i++) {
      if (songs[i].listens < songs[indexToCompare].listens) {
        swap(songs, indexToCompare, i);
      }
    }

    indexToCompare++;
  }

  return songs;
}

function swap(array, index1, index2) {
  let item1 = array[index1];
  let item2 = array[index2];
  array[index1] = item2;
  array[index2] = item1;
}

Try it out in JSBin

Speed and Big O Notation

In terms of speed, Selection Sort isn't very fast. In computer science, Big O notation indicates the speed of an algorithm, but not in seconds, minutes, or hours. Big O notation indicates the speed of an algorithm by the number of operations it will make for a given input size (the number of songs in our example). This lets you compare algorithms and see how the number of operations grow for a given input size.

In Big O notation, the O stands for operations and n stands for the input size, and it gives you a general idea of the number of operations. If an algorithm is O(n), this means for a list of size n, it will take n operations. The algorithm grows linearly.

So what is the Big O notation for the Selection Sort algorithm? Selection Sort takes O(n x n) time or O(n²) time. This means that the algorithm grows quadratically. Why is this?

For each item in the list, we're looping over the list again. Now you might think, isn't the number of elements we're checking each time decreasing? Yes that is true, but based on certain rules in Big O Notation, it comes out to O(n²) time. For those who are interested in how this works out, continue reading.

If we think about how many iterations we're doing, the first time is 5, the second time is 4, the third time is 3, and so on until we get to 0.

5 + 4 + 3 + 2 + 1 = 15

We could express the above this like:

5 + (5-1) + (5-2) + (5-3) + (5-4) = S

or more generically:

n + (n-1) + (n-2) + ... + 2 + 1 = S

So looking at this polynomial equation, my first question was, how do you derive n² from this? After some help from a few smart friends, here is how it works out. Let's say n is equal to 4. The polynomial equation would be:

n + (n-1) + 2 + 1 = S

Now take that equation and add it to itself, but reverse the terms:

n +  (n-1) +   2   + 1 = S
 1 +   2    + (n-1) + n = S
==================================
(n+1) + (n+1) + (n+1) + (n+1) = 2S

Notice how this comes out to 4 pairs of n + 1? We can now write this as:

n(n+1) = 2S
(n^2 + n) / 2 = S

In Big O Notation, constants like dividing by 2 are usually ignored, because if two different algorithms have different Big O runtimes, the constant ends up being insignificant. Sometimes they do make a difference though. So that leaves us with:

(n^2 + n) = S

What about the extra n? Well the n² is much larger than n when n is sufficiently large, so we can ignore that too because n² will dominate the runtime.

In the equation (n² + n) = S, we can consider n² as f(n) and n as g(n), so the runtime is O(f(n) + g(n)).

One Big O Notation rule is:

If f(n) > g(n) for large n, then O(f(n) + g(n)) = O(f(n))

Thus, we can drop the n and we're left with just n².

Conclusion

Selection sort is just one sorting algorithm and it isn't very fast. In a future post, we'll look a faster sorting algorithm called Quicksort. Stayed tuned for the next post in the Computer Science in JavaScript series.