Write a C Program to Implement the Insertion Sort Algorithm

by

Aim:

Write a C Program to To sort n number using Bubble sort.

Theory:

Description:

  • Insertion sort is based on the idea that one element from the input elements is consumed in each iteration to find its correct position i.e, the position to which it belongs in a sorted array.
  • It iterates the input elements by growing the sorted array at each iteration.
  • It compares the current element with the largest value in the sorted array. If the current element is greater, then it leaves the element in its place and moves on to the next element else it finds its correct position in the sorted array and moves it to that position.
  • This is done by shifting all the elements, which are larger than the current element, in the sorted array to one position ahead

Algorithm:

  • Step 1 − If it is the first element, it is already sorted. Return 1;
  • Step 2 − Pick the next element
  • Step 3 − Compare with all elements in the sorted sub-list
  • Step 4 − Shift all the elements in the sorted sub-list that is greater than the value to be sorted
  • Step 5 − Insert the value
  • Step 6 − Repeat until the list is sorted

Program:

#include <stdio.h>
#define size 100
void insertion_sort(int arr[], int n);
void main()
{
int arr[size], i, n;
printf("\n Enter the number of elements in the array: ");
scanf("%d", &n);
printf("\n Enter the elements of the array: ");
for(i=0;i<n;i++)
{
scanf("%d", &arr[i]);
}
insertion_sort(arr, n);
printf("\n The sorted array is: \n");
for(i=0;i<n;i++)
printf(" %d\t", arr[i]);

}
void insertion_sort(int arr[], int n)
{
int i, j, temp;
for(i=1;i<n;i++)
{
temp = arr[i];
j = i-1;
while((temp < arr[j]) && (j>=0))
{
arr[j+1] = arr[j];
j--;
}
arr[j+1] = temp;
}
}

Execution:

Input:
10 8 9 6 7 5 500 1 50 23 76

Output:

Enter the number of elements in the array: 
Enter the elements of the array: 
The sorted array is: 
1	 5	 6	 7	 8	 9	 23	 50	 76	 500

Result:

Thus, Implement of Insertion Sort was executed successfully.

Leave a Comment