Insertion Sort Program In C - Insertion Sort Code With Example

Insertion Sort Code In C With Example

 Here is an example of sorting exam papers according to student roll for understanding insertion sort. Suppose, 1, 2, 3, 4, 5,. . . . . , Exam papers are arranged in i - 1 format. Now, one will insert the n-th exam paper so that it is sorted according to the student's roll. First of all, is the i-1 paper smaller than the student roll of the new exam paper? Then the new paper will be inserted where it is. And if not, then (i-1)-th exam paper has to be brought in the i-th position and compared with i-2. This way one has to check the rest of the (i-n)-th papers one by one.


Now insertion sort will be implemented. 

Input: How many numbers will be taken in the first input? Suppose we take n number in an array. 

Output: The output will be a sorted series of n numbers. 


Solution:

Step 1: The first step is to declare the variable. We will work with integer variables to solve this problem. Then what will be the variables? 

n variable int n for n number 

The array of n numbers will be array_name int array_name [500] 

Temp Variable int temp to keep the temporary value 

Two variable int i and j for loop iteration,Then the declared variables are here,


int n, i, j, array_num[500], temp;


Step 2: This step will tell you what input to take.

n will be the input of the number

The array will be the input of n number (loop will run up to n).


    scanf("%d", &n);

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

    {

        scanf("%d", &array_num[i]);

    }


Step 3: Now move on to the main part of the insertion sort. First, a loop will run up to the n number. The array inside this loop has to be sorted compared to the previous number. For this, you have to run a while loop inside the for loop


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

    {

        while(j && array_num[j] &&temp)

       {

       }

    }


Step 4: Each number needs to have a temp variable as well as the number of the previous position. So, inside the for loop.


temp = array_num[i];


Step 5: Now we will continue to compare the variables temp and variable and sorted until the number of n loops is finished. We will continue to increase or decrease the variables i and j variables to check the previous and next numbers continuously. 


temp=array_num[i];

        j=i-1;


array_num[j+1]=array_num[j];

            j--;


array_num[j+1]=temp;


Step 6: In the last step we will print the sorted array by running n number loops.


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

    {

        printf("%d ", array_num[i]);

    }



Ok. Our full program is here. The insertion sort in c.



#include<stdio.h>

int main()

{

    int n, i, j, array_num[500], temp;

    scanf("%d", &n);

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

    {

        scanf("%d", &array_num[i]);

    }

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

    {

        temp=array_num[i];

        j=i-1;

        while(j>=1 && array_num[j]>temp)

        {

            array_num[j+1]=array_num[j];

            j--;

        }

        array_num[j+1]=temp;

    }

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

    {

        printf("%d ", array_num[i]);

    }

    return 0;

}




Sample Input:

5

90 70 6 3 2


Sample Output:

2 3 6 70 90



Time Complexity of Insertion Sort has been discussed in this link.

Post a Comment

Previous Post Next Post