Insertion sort in Data Structures

Insertion sort

Suppose an array ‘A’ with ‘n’ elements A[0]. A910,A[20],---------A[N-1] is in memory. The insertion sort algorithm in data structures scans ‘A; from A[0] to A[N-1] insert each element A[k] into its proper position in the previously sorted sub array A[0],A[1],A[2]----

A[K]                      That is

pass1                   A[0] by itself ip trivially sorted.

pass2                   A[1] is inserted either before or after aA[0]

So that : A[0],A[1] is sorted

pass3: A[2] is inserted into its proper place in

A[1] A[2], that is before A[0] between A[0]

A[1] or after A[1], so that : A[0],A[1],A[2] is sorted

pass4: [3] is inserted into its proper place in A[1],A[2] so that : A[0],A[1],A[2],A[3] is sorted.

PassN : A[N] is inserted into its proper place in A[1],A[2],-------A[N-1] so that : A[0],A[1]--- is sorted.

Example :

Insertion Sort Program

Implementation of insertion sort in data structures

# include <stdio.h>

# include <conio.h>

void main()

{

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

void insertion sort(int  a[10],int n);

clrscr();

printf(“Enter n value: ”);

scanf(“%d”,&n);

printf(“Enter the elements:\n”);

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

{

scanf(“%d”,&a[i]);

}

Insertion sort(a,n);

}

insertion sort(a,n);

printf(“The sorted elements are:\n”);

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

{

printf(“%5d”,a[i]);

}

}

void insertion sort (int a[20], int n)

{

int i,j,temp;

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

{

if(a[j]<a[j-1])

{

temp=a[j];

a[j]=a[j-1];

a[j-1]=temp;

}

}

}

}

output :

Enter ‘n’ value : 5

Enter the elements:     2       4       3       1       5

The elements are :  2   3       4       5

Time complexity :