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 j 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.