How Does Insertion sort work? Everything you should know

In the last article, we talked about the Computer network. Here we are going to talk about types of sorting and mainly insertion sorting. We find many methods to sort something which is not in order. There are many types of sorting, such as insertion sorting and selection sorting. If we apply selection sort, we sort the elements at the start on the left, and we don’t start from the end of the subarray.

Image result for insertion sort"

Card game example:

We will give you an example to explain sorting. For example, you are playing a card game where all the cards are in sequence means sorted. If someone adds one more card to the sorted cards, it must not be in series, and you need to arrange it in order. You will put the card into its right place. The purpose of the arrangement is to sort out all the cards into their position. The main thing in the selection sort is that the non-sorted element added to the sorted array is not smaller as compared to the sorted ones. But in this example (Card game), the new card adding may be smaller than some of the existing ones. You will check the right place of the new card and put it to maintain them in sequence. Once the card is placed in its correct position, you get the sorted cards again. If someone gives you another card, you’ll repeat the same process for all the new cards.

Let’s make it easier: For example, you have five cards numbered 2, 3,5,6, and 7. I add one more card with number “4” and say to put it into the correct position. If you put it one number before seven, you won’t get the sequence, and if you put it after the digit two, still it’s not in series. So, you’ll start finding that what’s the right position which must be a number less and near to the value of digit “4” to sort. The process for insertion sort works the same.

Internal and external sorting:

You’ll find two types of sorting based on storage. One is called internal sorting, and the other is external sorting. If the number of data is small and can fit into the internal storage, it is called internal sorting. If the number is large enough that needs extra storage and is stored in the external storage is called external sorting.

Insertion sort and Algorithm:

Insertion sort is a sorting algorithm. The process remains the same that putting the digit into its right position.

Characteristics of Insertion sort:

The following are some of the main features of insertion sort.

  • If you want to sort smaller value digits, insertion sort works better, but for more extensive data set, it doesn’t work better because one can’t order such a large number
  • If half of the array is already sorted the insertion sort in the unsorted ones is done after a few steps easily
  • You can quickly get the sorted array through insertion sort, unlike selection sort and Bubble sort algorithm, which are okay but not as compared to this. Moreover, it is not complex to solve
  • It doesn’t change the place of those digits which are constant

How does insertion sort work?

You can easily arrange digits into its place through insertion sort. For example, we have an array of figures arranged from smaller to higher numbers, but in the end, one digit is lower, which should be placed on the numbers in the left as it’s from lesser to higher. 

A number arranged in an array is, for example, digits 1, 2, 3,4,5, 8,9,11, and 7… Here we see that the numbers from 1 to 11 are arranged in order, but the number at the end isn’t. We need to put the digit “7” in sequence so that we will apply the insertion sort method. 

We will take the number 7 and move it from right to left step by step. In the first step, we will compare the number “7” with the second last number. We want to put the figure “7” after such a digit, which is smaller and near in value. Here “11” is greater than “7,” so we will move towards 9. Number “9” is also greater than “7,” so we will move towards number “8”.   

After comparing this number, the digit “8” is greater than “7” so we can’t put “7” after “8” so we will move towards the figure 5. 

Here the digit 5 is smaller in value than 7 and near to it, so we will put the digit seven after figure 5. The whole process involved a few steps. 

Example problem no.1:

The example given above is to explain the whole process of insertion sort. In the insertion sort, we use almost the same method to bring the numbers in order. To explain further, we will give the example of insertion sort.

For instance, we have an array of numbers to sort out. We will start with the index one. We won’t start from the index 0 because the first element is in order as it has no comparison with others. As we explain earlier through card game where every time a new position is vacant which we relate to the new card given to you. You need to place the digit into the right place in insertion sort, just like we did in the selection sort.

For example, we have an array of index where index from 0 to 5 is sorted, means the digits there are arranged from smaller to greater, and there is no unsorted digit. But we must arrange after the index 5 mean the figure in index six is not place in order. We must do this to get the whole array from 0 to 6 sorted. The subarray below after sorting out is:

0 1 2 3 4 5 6
1 2 4 5 8 9 12

The array shown above after sorting it out but how is it sorted out? Here you will find it through insertion sort in 5 easy steps:

0 1 2 3 4 5 6
1 2 5 8 9 12 4

We must sort this array where the digit ‘’4’’ is placed in a wrong position.

 Step no 1:

To take the start we would take the element into the right and compare it with the digits on the left side. We will make an extra space bellow the subarrays and start moving the box with the figure arrange it in order form right to left. We will slide the number ‘’4’’ in position ‘’6’’ in the extra box.

0 1 2 3 4 5 6
1 2 5 8 9 12 4
4

We call the extra box an ‘’Index E’’ where we put the digit four below the array. We will slide the index E from index six towards Index 5 to check if the digit is less than that digit in index 5. If the figure is less, we will put it thereafter it. In this case, if we check the number in index 5, it is greater than in index E=4, so we will slide it towards index 4. We will put the number ‘’12’’ twice in the index 5 and 6.

0 1 2 3 4 5 6
1 2 5 8 9 12 12
4

Step no. 2:

In the second step, we slide index E towards index 4 to check if index4 is smaller than it. After sliding we find that index E is lower and the index4 is higher so we can’t order it here in sequence because we want to order the numbers from left to right from smaller to greater, and we will put the number ‘’9’’ twice in the index 4 and 5 as follows:

0 1 2 3 4 5 6
1 2 5 8 9 9 12
4

Step no 3:

In the third step, we will slide index E towards index3 to check if it fits there, and we found that it’s still smaller than index3 and we want index3 to be smaller than index E. We will put the number 8 under index3 and index4 twice. And slide index E towards index3.

0 1 2 3 4 5 6
1 2 5 8 8 9 12
4

Step no 4:

In the fourth step, we will slide the index E towards index 2 to check if it fits there, but we find that index2 is greater than index E so it won’t fix here. We put the number ‘’5’’ in index2 twice and move index E towards the left to check there.

0 1 2 3 4 5 6
1 2 5 5 8 9 12
4

Step no. 5:

In the fifth step, we check that by sliding index E towards index1, the index E fits or not. We will check if the value of index1 is smaller than the index E than we must put index E after index1 on its right. Here the digit of index1 is ‘’2,’’ and the value of index E is ‘’4’’. Congratulations!! You have solved it!! Now we will put the number ‘’4’’ in index ‘’2’’ … now see what happens.

0 1 2 3 4 5 6
1 2 4 5 8 9 12

Now you see that the array is sorted with the above steps. We hope so you have understood the whole process. In short, the entire process is like:

0 1 2 3 4 5 6
1 2 5 8 9 12 4
             
1 2 5 8 9 12 12
            4
1 2 5 8 9 9 12
          4  
1 2 5 8 8 9 12
        4    
1 2 5 5 8 9 12
      4      
1 2 2 5 8 9 12
    4        
1 2 4 5 8 9 12

Example problem no. 2:

We will take another example to explain it further. For example, we have digits 1,2,3,6,15,11,12, 13. This problem is a little different from example no 1. The position of the digit there was in the end. Let’s sort this.

0 1 2 3 4 5 6 7
1 2 3 6 7 11 5 13

Above is the unsorted array because the number ‘’12’’ is not orderly mannered.

In the first step, we will make an extra box to put the word which is in its wrong position, i.e.‘’5’’. Put the number ‘13’ twice. We will compare the digit 13 and 5 as we want the number 13 to smaller than 5, but it’s not possible, so we will move towards the digit 11.

0 1 2 3 4 5 6 7
1 2 3 6 7 11 13 13
5

In the second step, we move to digit 11 and compare with the digit five after sliding the number 5 towards index 6. We see that the digit 11 here is still greater than figure five, so we will move one box left. We will put the number 11 twice.

0 1 2 3 4 5 6 7
1 2 3 6 7 11 11 13
5

In the third step, after sliding the digit towards the figure seven we still found that the number 7 is greater than five so we can’t put the number 5 after 7. We will put the digit 7 twice here.

0 1 2 3 4 5 6 7
1 2 3 6 7 7 11 13
5

In the fourth step, we will move the digit five towards the index4 and compare it with the figure 6. We again found that the digit 6 is greater in number, so placing the number 5 after digit 6 is not a good idea. We will put digit six twice and move towards the index 3 to compare figure 5 with 3.

0 1 2 3 4 5 6 7
1 2 3 6 6 7 11 13
5

We will move towards index 3 to compare digit five and digit 3. Here we found that the number 3 is smaller than figure 5 and near to its value, so it would be a better idea to put the digit five after digit 3. Index 3 is the right position for digit 5.

0 1 2 3 4 5 6 7
1 2 3 5 6 7 11 13

Pin It on Pinterest