Insetion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands.It is a sorting algorithm that places an unsorted element at at its suitable place in each iteration.This works by swaping elements
Working Procedure:
Lets take an array
step 1:
9 5 1 4 3
The 1st element in the array is assumed to be sorted.So sorting the second element and store it seprately in key.We have to compare key with the first element.If the 1st element is greater than key then key is placed in front of the first element
9 5 1 4 3
5 9 1 4 3
step 2:
5 9 1 4 3
then key is on 1
5 1 9 4 3
1 5 9 4 3
Step 3:
1 5 9 4 3
1 5 4 9 3
1 4 5 9 3
Step 4:
1 4 5 9 3
1 4 5 3 9
1 4 3 5 9
1 3 4 5 9
Insertion Sort Algorithm:
insertionSort(array)
mark first element as sorted
for each unsorted element x
'extract' the element x
for j<last sortedIndex down to 0
if current element j>n
move sorted element to the right by 1
break loop and insert x here an insertSort
Implementation:
#include <math.h>
#include <stdio.h>
void insertionSort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
void printArray(int arr[], int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main()
{
int arr[] = { 12, 11, 13, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
printArray(arr, n);
return 0;
}
0 Comments