Translator: Mcbai

The original link

JS programming: Insert sort

To become a better developer, understanding data structures, algorithms, and basic programming ideas is a must. Most of these problems are solved by modern tools and libraries, but having a deeper understanding of these areas will greatly broaden your horizons for software development.

It’s quite difficult for me to master these concepts because I rarely use them in my daily work. This series of articles I am writing is intended to improve my understanding of these aspects and those like me.

What is insertion sort?

Insertion sort is another common sorting algorithm, although it is not as high-performance as quicksort or merge sort. It works by dividing an array into two parts — those that are sorted and those that are not. We don’t know if each item is already in the right place, so we’ll sort from the first item.

And then we check the other items in the array. For each item in the sorted array, we have to find its proper location. The way to do it is to find the first item smaller than it, or to the beginning of the list. Maybe it’s better if I just show you a practical example. Sorted items are bolded:

**5**, 9, 13, 4, 1, 6Copy the code

**5, 9,** 13, 4, 1, 6 // 9 > 5, so we don't moveCopy the code

**5, 9, 13**, 4, 1, 6 // 13 > 9 we also do not moveCopy the code

**4, 5, 9, 13**, 1, 6 // All items compared to 4, up to the beginning of the arrayCopy the code

**1, 4, 5, 9, 13**, 6 // All items are compared to 1, up to the beginning of the arrayCopy the code

**1, 4, 5, 6, 9, 13** // The first term 5 less than 6, put the 6 in front of itCopy the code

It is a

What’s special about insertion sort is that we’re not swapping terms, even though it looks like we’re swapping and moving them. What happens is that we loop through the sorted part and find the first smaller item (or the beginning of the array) and put our item there. What did we do to them before that? As we loop through each item, each item with a larger value is actually moved one bit forward (well, not moved, copied) to make room for the current item.

It is best to give a code presentation of the actual algorithm so that you can get a better idea of what is going on:

function insertionSort (items) {
  for (var i = 0; i < items.length; i++) {
    let value = items[i]
    // Store the value of the current item so that it can be placed in the correct location
    for (var j = i - 1; j > -1 && items[j] > value; j--) {
      // Iterate over sorted items in the array (from the current item to the beginning of the array)
      // Copy each item to the next location
      items[j + 1] = items[j]
    }
    // At the last item, we should save the value of the currently sorted item
    items[j + 1] = value
  }
  return list
}
const list = [54.26.93.17.77.31.44.55.20]
console.log(insertionSort(list)) // [17, 20, 26, 31, 44, 54, 55, 77, 93]
Copy the code

Once you understand the concept, it’s not at all difficult to transfer it to code. I think this is a much simpler implementation of the algorithm. Spend some time on it, write it down on a piece of paper, grab the idea, and then code it.

Thanks for reading, if you are looking for more JS stuff, I am currently writing a series of articles about these. If you need JS comprehensive content, you can check out my profile.

JS programming:

Recursive: hackernoon.com/programming… Merge sort: medium.com/kondovalex… Dichotomy: medium.com/kondovalex… Insert sort: [medium.com/@KondovAlex…