Sort by repeatedly taking the next item and inserting it into the final data structure
in its proper order with respect to items already inserted.
It inserts each element of the array into its proper position.
Insertion sort is used by card players when sorting.
If he wants to sort the cards, he take card
in its proper order with respect to items already inserted.
It inserts each element of the array into its proper position.
Take number 4
Compare with number 3
These two elements has proper order
Take number 2
Compare with number 4
These two values must be sorted
Move value 4 to the position where number 2 was
Move value 3 to the position where number 3 was
Put value 2 at position of value 3
Source code examples
#include "stdafx.h"
#include
#include
#include
#include
#include
#include
#define NUM 4
int arr[NUM]={3,4,2,1};
void insertion_sort(int x[],int length)
{
int key,i;
for(int j=1;j{
// Get value which will be compared ( position + 1 )
key=x[j];
// Get position before ( position - 1 )
i=j-1;
// if the value at position - 1 ) is smaller
while( x[i] > key && i>=0)
{
// move values to the right side
x[i+1]=x[i];
i--;
}
// and here puts value which was compared
x[i+1]=key;
}
}
int main()
{
insertion_sort(arr,NUM);
return 0;
}