Tutorial

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

Published on February 3, 2020
Default avatar

By Joshua Hall

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

Thanks for learning with the DigitalOcean Community. Check out our offerings for compute, storage, networking, and managed databases.

Learn more about us


About the authors
Default avatar
Joshua Hall

author

Still looking for an answer?

Ask a questionSearch for more help

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!

Try DigitalOcean for free

Click below to sign up and get $200 of credit to try our products over 60 days!

Sign up

Join the Tech Talk
Success! Thank you! Please check your email for further details.

Please complete your information!

Get our biweekly newsletter

Sign up for Infrastructure as a Newsletter.

Hollie's Hub for Good

Working on improving health and education, reducing inequality, and spurring economic growth? We'd like to help.

Become a contributor

Get paid to write technical tutorials and select a tech-focused charity to receive a matching donation.

Welcome to the developer cloud

DigitalOcean makes it simple to launch in the cloud and scale up as you grow — whether you're running one virtual machine or ten thousand.

Learn more
DigitalOcean Cloud Control Panel