Hey guys, what is up. In this particular post, we will be talking about insertion sort. It’s working, insertion sort algorithm, and program.

Insertion sort:

Insertion sort is one of the most simple sorting methods. We all have seen playing cards. When we play cards we sort one card at a time. Similarly, insertion sort works in the same way. The array elements are continuously converted into an unsorted and sorted manner. Later, this element is swapped by the neighboring array element. Array elements that are unsorted are taken and put in their desired position. In this way sorting takes place.

Working:

Firstly, the outer loop starts from 1 and it runs till i is less than a total number of elements. Then the value of the first element is stored in the third variable. And j is given value i-1. If the second element is smaller than the first element then the value of the second array element is given to the first array element. In this way, space is created for swapping. Now the inner loop terminates. Now the second space is filled up with the first element and so on.

ARRAYSTEP 1STAIR 2STAGE 3PASS 4STEP 5
432221
343332
224443
12121212104
101010101210
1111112
method insertion sort

Advantages of Insertion sort:

  1. It is easily executed
  2. Also, it is well organized whenever we use a small amount of data
  3. Moreover, the extra storage space requirement is very less.
  4. Also, it is a live sorting method.
  5. Basically, new elements are sorted when they are taken from the user.
  6. Basically, it is more speedy than all other types of sorting algorithms.

Insertion sort algorithm:

Step 1: i=1

Step 2: Repeat steps from 2 to 9 using while loop with i<n

Stair 3: j=i-1

Step 4: temp=A[i]

Step 5: Repeat steps from 5 to 7 using while loop with j>=0 && A[j] > temp

Stair 6: A[j+1]=A[j]

Step 7: j – –

            {End of inner loop}

Stair 8: A[j] = temp

Step 9: i=i++

            {End of outer loop}

Step 10: Stop

Insertion sort program:

insertion sort algorithm program output

#include <iostream.h>

#include <conio.h>

int main()

{

            clrscr();

            const max=40;

            int a[max], n, i, j, temp;

            cout<<“Enter the dimension of array (<max= “;

            cin>>n;

            cout<<“Enter elements in any order: “;

            for (i=0; i<n; i++)

            {

                        cout<<” a[“<<i<<“]= “;

                        cin>>a[i];

            }

            i=1;

            while ( i< n)

            {

                        temp=a[i] , j=i-1;

                        while( j>=0 && a[j]>temp )

                        {

                                    a[j+1] = a[j];

                                    j=j-1;

                        }

                        a[j+1]=temp;

                        i=i+1;

            }

            i=0;

            cout<<endl<<endl<<“Sorted array”<<endl;

            for (i=0; i<n; i++)

            {

                        cout<<” a[“<<i<<“]= “;

                        cout<<a[i];

            }

            return 0;

}

In the upcoming post, you will be getting information related to the working of any of the sensors. If you haven’t read our previous post on selection sort and bubble sort then go and read this. Also, stay tuned for the upcoming post. Also, for other C++ notes and topics check out our menu. Moreover, all things are updated in the menu section. You can also follow us on social media platforms that can help you in getting all information regarding the latest posts. 

Categories:

0 Comments

Leave a Reply

Avatar placeholder

Your email address will not be published. Required fields are marked *