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 :