I have seen couple of students who use swap in insertion sort to sort an array.Insertion sort is an example of exchange sort ,we don't swap two elements to sort an array ,instead of this we shift elements if ith element is greater than i+1th element to sort an array.It works on simple concept:-
Store the ith element in temporary variable and shift element until you find the element smaller than this element towards 0 index position.Here is the C Program to find insertion sort:-
_________________________________________________________________________________
#include <stdio.h>
#include <string.h>
main()
{
int arrSize,i;
printf("Enter Size of array:");
scanf("%d",&arrSize);
int array[arrSize];
for(i=0;i<arrSize;i++){
scanf("%d",&array[i]);
}
int temp,j;
for(i=1;i<arrSize;i++){
temp=array[i];
for(j=i;j>0;j--){
if(temp<array[j-1]){
array[j]=array[j-1];
}else{break;}
}
array[j]=temp;
}
printf("Sorted Array is:\n");
for(i=0;i<arrSize;i++){
printf("%d",array[i]);
}
}
___________________________________________________________________________
temp=array[i];
ReplyDeletefor(j=i;j>0;j--){
if(temp<array[j-1]){
array[j]=array[j-1];
}else{break;}
}
array[j]=temp;
temp=array[i];
ReplyDeletefor(j=i;j>0;j--){
if(temp<array[j-1]){
array[j]=array[j-1];
}else{break;}
}
array[j]=temp;
please explain this code in detail
@kaju:-this code will put ith element in temp and run the code if any i-1 th element is greater than ith element.............at the same time.....it will shift all the element which is greater than ith element.to right.......
ReplyDeleteTill at the end of inner loop....it will put the ith element in the jth element position.
If any element is not greater than i th element then it breaks the inner loop .