❮❮ PREV NEXT ❯❯

INSERTION SORT

Insertion Sort is a sorting technique where we pick an element and place it in the right location so that it is sorted. It is same as organizing a pack of card while playing a card game.

Let us simplify with the below example :

Say, there are 6 students in a class and all are sitting in a single row. Now, let's assume you are the class teacher and your task is to make the students sit based on their roll numbers.

And since these are naughty students, they have sat randomly in their seats.

Below is the way the students have sat :

i.e. Roll no 5 has sat in the 1st location, Roll 3 in the 2nd location and so on.

Now, if you follow the insertion sort algorithm to sort the students based on roll numbers, it would be as follows :

1. You start with the student in the 2nd location(Let's call this location a key) and compare his roll no with student of 1st location.

And found,

Roll no 3 is less than roll 5.

So, you have placed roll number 3 in 1st location and roll no 5 in 2nd location.

2. Then you start with the student in the 3rd location(Let's mark this location a key) and compare his roll number with the roll number of the student sitting in 2nd and 1st location.(1st and 2nd location is already sorted).

And found,

6 is greater than 5.
6 is also greater than 3.

So, roll number 6 will stay in 3rd location itself.

So, roll number 6 will stay in 3rd location itself.

3. Now, we start with the student in the 4th location(Let's mark this location with a key) and compare with 3rd, 2nd and 1st location.

And found,

2 is less than 6.

So, we swap roll 6 with 2.

Again we compared roll no 2 with 5 and found

5 is less than 2.

So, we swap roll 5 with 2.

Again we compared roll 2 with 3 and found

3 is less than 2.

So, we swap roll no 2 with 3.

4. Now, we will start with the 5th location(Let's mark this location a key). And compare roll no of 5th location student with 4th, 3rd, 2nd and 1st location.

And we have seen,

1 is less than 6.

So, we swap roll no 1 with 6.

Again, we can see,

1 is less than 5.

So, we swap roll no 1 with 5.

Now,

1 is less than 3.

So, we swap roll no 1 with 3.

Again,

1 is less than 2.

So, we swap roll no 1 with 2.

5. Then, we will start with the 6th location(Let's mark this location a key). And compare roll no of 6th location student with 5th, 4th, 3rd, 2nd and 1st location.

And we have seen,

4 is less than 6.

So, we swap roll no 4 with 6.

Again, we can see,

4 is less than 5.

So, we swap roll no 4 with 5.

Now,

4 is greater than 3.

And we don't have to swap anymore as the students are sorted based on their roll number.

So, that is exactly how Insertion Sort works.

Insertion Sort briefly

i.e.

1. You pick an element from the 2nd location, call it a key.

Then compare the key element (i.e. 3) with the elements on the left side. And place the key element (i.e. 3) in the appropriate place. Now, the elements in 1st and 2nd location is sorted.

2. Then we pick the element in the 3rd location and mark it as key.

Now, we compare this key element (i.e. 5) with the elements on the left side. And place the key element (i.e. 5) in the appropriate place, so that it is sorted.

We continue this process until all the elements are sorted.

❮❮ PREV NEXT ❯❯