What is insertion sort....?

what is insertion sort and develop a C program to sort a given array of integers in to descending order

What is insertion sort....?
Here you go


Insertion sort is a simple sorting algorithm, a comparison sort in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than the more advanced algorithms such as quicksort, heapsort, or merge sort, but it has various advantages:





* Simple to implement


* Efficient on (quite) small data sets


* Efficient on data sets which are already substantially sorted: it runs in O(n + d) time, where d is the number of inversions


* More efficient in practice than most other simple O(n2) algorithms such as selection sort or bubble sort: the average time is n2/4 and it is linear in the best case


* Stable (does not change the relative order of elements with equal keys)


* In-place (only requires a constant amount O(1) of extra memory space)


* It is an online algorithm, in that it can sort a list as it receives it.








************


%26lt;%26lt;insertion_sort%26gt;%26gt;=


/* Sort an array of integers */


void insertion_sort(int a[], int length)


{


int i;


for (i=0; i %26lt; length; i++)


{


insert a[i] into sorted sublist


}


}





///
Reply:Its a method of sorting the array variables in a program


the algorithm is same as the above guy has given


search a good computer book in order for a full detail
Reply:#include%26lt;stdio.h%26gt;


#include%26lt;conio.h%26gt;


#include%26lt;time.h%26gt;





void main()


{


int item, n,i,j,a[10];


clock_t start,end;


float duration;


clrscr();


printf("enter the total no of elements in the array\n");


scanf("%d",%26amp;n);


printf("enter the elements one by one\n");


for(i=0;i%26lt;n;i++)


scanf("%d",%26amp;a[i]);


start=clock();


for(i=1;i%26lt;n;i++)


{


item=a[i];


for(j=i-1;j%26gt;=0 %26amp;%26amp; item%26lt;a[j];j--)


{


a[j+1]=a[j];


}


a[j+1]=item;


}


delay(100);


end=clock();





duration=(end-start)/CLK_TCK;


printf("sorted array is \n");


for(i=0;i%26lt;n;i++)


printf("%d\n",a[i]);


printf("time required=%f",duration);





getch();


}