Beginner Sorting Algorithms in JavaScript: Bubble, Selection & Insertion Sort

Having your datasets arranged all willy-nilly will only add more time and resources to manage and search through. Whether your data is sorted or not will directly affect what search methods you can use and can mean the difference between a search taking a million operations or taking 10, like with Binary Search.

For simplicity’s sake, we’re only going to focus on sorting an array of numbers from least to greatest, but these algorithms are easily modifiable for other sorting goals. Keep in mind that these are more general concepts and patterns and less of a “how-to” for sorting data since your particular implementation may differ a lot but in the end it may conceptually resemble these patterns.

Here’s the practice array of 50 random numbers.

const unsortedArr = [31, 27, 28, 42, 13, 8, 11, 30, 17, 41, 15, 43, 1, 36, 9, 16, 20, 35, 48, 37, 7, 26, 34, 21, 22, 6, 29, 32, 49, 10, 12, 19, 24, 38, 5, 14, 44, 40, 3, 50, 46, 25, 18, 33, 47, 4, 45, 39, 23, 2];

Prerequisites

I’m going to be looking at everything through the lens of Big O Notation, so understanding how complexity grows over time will be very helpful.

Bubble Sort

This is the “Hello World” of sorting methods, nothing crazy but it gets the job done.

For each item in the array we want to check if the next item is larger, if it is then swap their indexes in the array. To avoid recomparing sorted numbers we’ll start from the back of the array while another for loop gets the preceding number. This way all of the largest values build up, or “bubbles up”, on the end.

Graphic/Animation thanks to VisuAlgo.net

Our version works in reverse from the animation, but it’s close enough.

const bubble = arr => {
  const swap = (list, a, b) => [list[a], list[b]] = [list[b], list[a]];

  for (let i = arr.length; i > 0; i--) {
    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) swap(arr, j, j + 1);
    };
  };

  return arr;
};

console.log(bubble(unsortedArr));

Selection Sort

Selection sort works like the opposite of Bubble sort, while bubble sorting is pushing all of the largest values to the end now we’re going to push the minimum values to the start.

Every time it loops over the array it selects the smallest value, if it finds a lower value that then that becomes the new lowest value. When the loop is done it’ll take that minimum and put it on the front of the array before starting the loop again. This way the lowest value of each iteration is stacked onto the front until the whole array is sorted.

Graphic/Animation thanks to VisuAlgo.net

const selection = arr => {
  const swap = (list, a, b) => [list[a], list[b]] = [list[b], list[a]];

  arr.forEach((item, i) => {
    let min = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[min]) min = j;
    };
    swap(arr, i, min);
  });

  return arr;
};

console.log(selection(unsortedArr));

Insertion Sort

My personal favorite and the most performant of the three, insertion sort, is more similar to how you would sort something by hand.

We look at the array as two parts, the sorted and unsorted, with every time we find a new value we loop back to find its place in the sorted half. With each addition our sorted group grows until it is the whole array.

Graphic/Animation thanks to VisuAlgo.net

const insertion = arr => {
  arr.forEach((item, i) => {
    let num = arr[i];
    let j;

    for (j = i - 1; j >= 0 && arr[j] > num; j--) {
      arr[j + 1] = arr[j];
    };
    arr[j + 1] = num;
  });

  return arr;
};

console.log(insertion(unsortedArr));

Comparison

One problem with using Big O Notation for comparing algorithms is that it’s based on the worse-case scenario, which may be the same across algorithms giving the false illusion that they’re equal. While Bubble, Selection, and Insertion sorts are all O(n^2), that doesn’t tell us much about the average or best case scenario or how they vary with the data structure.

Insertion sort wins every time. It also has the benefit of not needing to have the whole array before starting, which allows you to sort things in real-time as data comes in.

Keep this in mind because you shouldn’t decide which algorithm is “best” before considering how your data is already organized.

Conclusion

These three are far from the best solutions to efficiently sorting large amounts of data, but they are some of the most intuitive to dip your toes into what can be an overwhelming ocean. 🌊