// Tutorial //

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

Published on February 3, 2020
Default avatar
By Joshua Hall
Developer and author at DigitalOcean.
Beginner Sorting Algorithms in JavaScript: Bubble, Selection & Insertion Sort

While we believe that this content benefits our community, we have not yet thoroughly reviewed it. If you have any suggestions for improvements, please let us know by clicking the “report an issue“ button at the bottom of the tutorial.

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.

Bubble Sort Animation

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.

Selection Sort Animation

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.

Insertion Sort Animation

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. 🌊


Want to learn more? Join the DigitalOcean Community!

Join our DigitalOcean community of over a million developers for free! Get help and share knowledge in our Questions & Answers section, find tutorials and tools that will help you grow as a developer and scale your project or business, and subscribe to topics of interest.

Sign up
About the authors
Default avatar
Developer and author at DigitalOcean.

Still looking for an answer?

Was this helpful?
Leave a comment

This textbox defaults to using Markdown to format your answer.

You can type !ref in this text area to quickly search our full set of tutorials, documentation & marketplace offerings and insert the link!