Insertion Sort

Insertion sort

How it works: Imagine you are playing cards. Somebody is giving you cards one by one. When you are receiving card, you are planning to put them in a way so that the smaller one is on the left. This means you want to insert them in a sorted way

step-1: If the first card you are getting is 5. Just hold the card in your hand. you dont have to do anything.

step-2: If the second card is 2, you want to put it before 5 so that the two cards you have are sorted. When you are putting the card with number 2 at the left, you are changing the position of the card 5 from first position to second position. And then first position becomes available and you put 2 there.

step-3: If the third card is 4. you will start from second position. In the second position, you have card 5 which is bigger than 4. Hence you will move 5 to the third position. The next card to the left is 2 which is smaller than 4. Hence, you wont move 2. And you will insert card 4 in the second position.

step-4: Then you got 10. It is bigger than the previous card which is 5. Hence, you just add it at the last position.

step-5: The next card is 7. You just move the position of the card 10 to the right and insert card 7.

step-6: If the last card is 3. You will have to move 10 to the right as it is bigger than 3. and then you check with the next card to the left it is 7 which is bigger than 3. you move it to the right. similarly, you move 5, 4 to the right. And put the number 3 before 2 as 2 is smaller than 3.

congrats. you are done.

Code Insertion sort: Code is similar to the card and image above. It starts with the second element. Pick the second element to be inserted and then compare to the previous element. If the first one is bigger, move the first one to second position and second one at first.

Now first and second item is sorted.

Then, pick the third element and check whether the second element is bigger than the third. keep going similar way until you hit the first element or a element smaller than the element you are comparing with. When you get an item smaller than the picked item, you insert it.

super easy.

Code Explanation:

Below is a function that does insertion sort. In side the function you will see two loop. the first for loop is seleccting an item for the items array. the selected item is the picked card on your hand. It's called currentItem.

Now think, in a middle situation where you have picked the third card. this means all the card in the left are sorted. you have to find a position for the current card to be inserted. if the current card is smaller than any of the previous card it will be insterted before that

For this we run the second while loop. This loop goes backward upto 0 position. As 0 is the first position of the array

while running the while loop, if the item in the array is bigger than the currentItem, we move the item to the right. Think it as if you are inserting cards on your hand by looking into your available cards from right to left

function insertionSort(items) {

    for (var i=0; i < items.length; i++) {

        var currentItem = items[i];
        var j = i -1;

        while (j >= 0 && items[j] > currentItem) {
            items[j+1] = items[j];
            j--;
        }

        items[j+1] = currentItem;
    }

    return items;
}
		        

complexity: the worst case O(n2) and best case O(n)