# Insertion Sort using C Program

Insertion Sort

• Idea: Start at position 1 and move each element to the left until it is in the correct place
• At iteration i, the leftmost i elements are in sorted order.
• Sorts list by moving each element to its proper place.
• Efficient for sorting small numbers.
• In place sort: Takes an array A[0..n-1] (sequence of n elements) and arranges them in place, so that it is sorted.
• Attempts to improve high selection sort key comparisons.

Pseudo Code

```for i = 1; i < a.size(); i++

tmp = a[i]

for j = i; j > 0 && tmp < a[j-1]; j--

a[j] = a[j-1]

a[j] = tmp```

In this lesson we will learn how to write a source code in C programming language for doing simple Insertion sort using array in ascending order.

Question : Write a c program for insertion sort.

C Example

```/**
Insertion Sort Algorithm C Example by Codebind.com
*/
#include <stdio.h>
#include <stdlib.h>

void PrintArray(int *array, int n) {
for (int i = 0; i < n; ++i)
printf("%d ", array[i]);
printf("\n");
}

void InsertionSort(int arr[], int arr_size){
if(arr_size > 1){
int size = arr_size;
for(int i = 1; i < size; ++i){
int j = i - 1;
int key = arr[i];
while(j >= 0 && arr[j] > key){
arr[j+1] = arr[j];
--j;
}
arr[j+1] = key;
}
}
}

int main() {
int array[] = {94, 42, 50, 95, 333, 65, 54, 456, 1, 1234};
int n = sizeof(array)/sizeof(array[0]);

printf("Before Insertion Sort :\n");
PrintArray(array, n);

InsertionSort(array, n);

printf("After Insertion Sort :\n");
PrintArray(array, n);
return (0);
}

/*
OUTPUT
Before Insertion Sort :
94 42 50 95 333 65 54 456 1 2325
After Insertion Sort :
1 42 50 54 65 94 95 333 456 2325
*/
```