Sorting algorithms: JavaScript - Insertion Sort🚀
Tags: javascript, webdev, programming, codequality
Published: 2021-02-05 20:03:37

Table Of Contents
        * 🤓 [INTRODUCTION](#intro)
        * 👉🏻 [ABOUT INSERTION SORT ALGORITHM](#insertion)
        * 🃏 [PLAYING CARDS ANALOGY](#cards)
        * 🖖🏻 [PSEUDOCODE](#pseudo)
        * 🛠 [IMPLEMENTATION](#implement)
        * 👩🏻‍💻 [CODE](#code)
        * 🙏 [THANK YOU](#thank-you)


##🤓 INTRODUCTION <a name="intro"></a>

Top of the day, my dear coders! I hope you are all having a beautiful day. Welcome to another chapter of the Sorting algorithms with JavaScript series. Today we are talking about the Insertion Sort algorithm!

> The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. - Donald Knuth

Let's dive in! 🤿


##👉🏻 ABOUT INSERTION SORT ALGORITHM <a name="insertion"></a>

Insertion sort algorithm solves the sorting problem:
**Input:** A sequence of n numbers
**Output:** A permutation (reordering) of the input sequence

The numbers that we want to sort, are also known as **keys**. Input is usually an array of n elements.

Insertion sort algorithm is an efficient algorithm for sorting a small number of elements.


##🃏 PLAYING CARDS ANALOGY <a name="cards"></a>
Insertion sort works the way many people sort a hand of playing cards. 

**STEPS**
1. We start with an empty left hand and the cards face down on the table.  
2. We remove one card at a time from the table and insert it into the correct position in the left hand.
3. To find the correct position for a card, we compare it with each of the cards already in the hand (right to left)
4. At all times, the cards held in the left hand are sorted, and these cards were originally the top cards of the pile on the table


##🖖🏻 PSEUDOCODE <a name="pseudo"></a>
In this chapter, I will also introduce you to pseudocode. Pseudocode is an artificial and informal language that helps us programmers develop algorithms. Pseudocode is a "text-based" detail (algorithmic) design tool. The rules of Pseudocode are reasonably straightforward.

We will call this pseudocode (procedure) INSERTION-SORT-ALGO. It will take an array A[1...n], that contains a sequence of length n that is to be sorted. This procedure will rearrange the numbers within array A, with at most a constant number of them stored outside the array at any time.

```pseudocode
INSERTION-SORT-ALGO(A: array)
1 for j = 2 to A.length
2   key = A[j]
3   //Insert A[j] into the sorted sequence A[1...j-1]
4   i = j - 1
5   while i > 0 and A[i] > key
6      A[i+1] = A[i]
7      i = i - 1
8   A[i+1] = key
```
Let's say that our array A looks like this: [9, 5, 6, 12];
The iteration of the loop starting at 1 and ending at 8, in each iteration, the black rectangle holds the key taken from A[j] which is compared to its left-hand side elements.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/grb4u0k66wb576db4xth.png)


##🛠 IMPLEMENTATION <a name="implement"></a>
Let's see an implementation, but we will work with a larger dataset. For example, let our array be: [5, 9, 6, 12, 1, 2, 34, 15, 7]

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/xi6wwx9j89p0ce1mo3hs.png)

##👩🏻‍💻 CODE <a name="code"></a>
Play with the code! 🕺🏻
{% jsfiddle https://jsfiddle.net/codespresso/qpdjwyfb/19/ result,js,html,css %}


# 🙏 THANK YOU FOR READING!<a name="thank-you"></a>
References:
School notes...
School books...

Please leave a comment, tell me about you, about your work, comment your thoughts, connect with me! 

☕ SUPPORT ME AND KEEP ME FOCUSED!
<a href='https://ko-fi.com/Z8Z33D1HJ' target='_blank'><img height='36' style='border:0px;height:36px;' src='https://cdn.ko-fi.com/cdn/kofi4.png?v=2' border='0' alt='Buy Me a Coffee at ko-fi.com' /></a>

Have a nice time hacking! 😊

![folks](https://media.giphy.com/media/xUPOqo6E1XvWXwlCyQ/giphy.gif)