C Program for Insertion Sort

Insertion sort in C: Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is Adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(kn) when each element in the input is no more than k places away from its sorted position. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

• Worst complexity: n²
• Average complexity: n²
• Best complexity: n
• Space complexity: 1

Problem: Sort a random array of n integers (accept the value of n from user) in ascending order by using insertion sort algorithm

C program for insertion sort

// Aim: C program for insertion sort

#include <stdio.h>
#include <math.h>
 
/* Function to sort an array using insertion sort*/

void insertionSort(int arr[], int n)
{
   int i, key, j;
   for (i = 1; i < n; i++)
   {
       key = arr[i];
       j = i-1;
 
/* Move elements of arr[0..i-1], that are
          greater than key, to one position ahead
          of their current position */
     
       while (j >= 0 && arr[j] < key)
       {
           arr[j+1] = arr[j];
           j = j-1;
       }
       arr[j+1] = key;
   }
}
 
// A utility function to print an array of size n
void printArray(int arr[], int n)
{
   int i;
   for (i=0; i < n; i++)
       printf("%d ", arr[i]);
   printf("\n");
}
 
 
/* Driver program to test insertion sort */
int main()
{
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
 
    insertionSort(arr, n);
    printArray(arr, n);
 
    return 0;
}

Get This Program:  

Problem: Sort a random array of n integers (accept the value of n from user) in ascending order by using insertion sort algorithm.

C program to sort a random array in ascending order using insertion sort

/* Aim: C Program to sort a random array in ascending order using insertion sort */

#include 
#include 

// Function to display array

void DisplayArray(int arr[],int n)
{
 int i;

 for(i=0;i<n;i++)
 printf(" %d ",arr[i]);
}

// Function to generate random array

void Generate(int *arr, int n)
{
 int i;

 for(i=0;i<n;i++)
 arr[i]=rand()%100;


}


// Function for insertion sort

void InsertionSort(int arr[], int n)
{

 int Rvalue,i,j;

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

 Rvalue=arr[i];

 j=i-1;

 
 while( j>=0 && arr[j]>Rvalue)
 {
  arr[j+1]=arr[j];
  j=j-1;
 }

 arr[j+1]=Rvalue;

 }
}

// main() function to test the insertion sort
 
void main()
{
 int arr[100],n;

 printf("\n Enter the size of array:- ");
 scanf("%d",&n);

 Generate(arr,n); // Generating a random array
 
 printf("\n The random array: ");
 DisplayArray(arr,n); // Displaying the array

 InsertionSort(arr,n); // Sorting the array

 printf("\n The sorted array: ");
 DisplayArray(arr,n); // Displaying the sorted array

 printf("\n");

}

/* Output of above code:-

 Enter the size of array:- 5

 The random array:  83 86 77 15 93

 The sorted array:  15 77 83 86 93

*/

Get This Program:  

Problem: Sort a random array in descending order using insertion sort.

Que. What modification is required to insertion sort to sort the integers in descending order?
Answer: We just have check whether the integer before key is less than key or not. If it is, we have to swap it.

C program to sort random array in descending order using insertion sort

/* C Program to sort a random array in descending order using insertion sort */

#include<stdio.h>
#include<stdlib.h>

void DisplayArray(int arr[],int n)
{
	int i;

	for(i=0;i<n;i++)
		printf(" %d ",arr[i]);
}

void Generate(int *arr, int n)
{
	int i;

	for(i=0;i<n;i++)
		arr[i]=rand()%100;
}

void InsertionSort(int arr[], int n)
{

	int Key,i,j;

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

		Key=arr[i];

		j=i-1;

		while( j>=0 && arr[j]<Key)
		{
			arr[j+1]=arr[j];
			j=j-1;
		}

		arr[j+1]=Key;
	}
}
 
int main()
{
	int arr[100],n;

	printf("\n Enter the size of array:- ");
	scanf("%d",&n);

	Generate(arr,n); // Generating a random array
 
	printf("\n The random array: ");
	DisplayArray(arr,n); // Displaying the array

	InsertionSort(arr,n); // Sorting the array

	printf("\n The sorted array: ");
	DisplayArray(arr,n); // Displaying the sorted array

	printf("\n");

	return 0;
}

/* Output of above code:- 

 Enter the size of array:- 5                                                                                                 
                                                                                                                             
 The random array:  83  86  77  15  93                                                                                       
 The sorted array:  93  86  83  77  15

*/

Get This Program: