# Insertion Sort Algorithm

Hello, In my previous article i talked about the selection sort algorithm you can reach by clicking here and in this article i try to make **Insertion Sort Algorithm**. In the insertion sort algorithm we pass the first element of the array and we think that that data is the smallest in the array. Rest of the data array, we consider that they are orderly and we checking the conditions. Algorithm complexity of the Insertion Sort is : In the best case **n** and in the worst case **n ^{2}**. For the make example to understand better, think about a array and the data of the array is this [3,1,6,5,7,8,2,4].

We pass the first item in the array and checking the conditions.

3|1,6,5,7,8,2,4 Look at the array and if the second item smaller than the first item, we change the their order.

1,3|6,5,7,8,2,4 The other item is bigger than the second item, we do not change the order and we look the other item.

1,3,6|5,7,8,2,4 We change the 5 and 6 order because 5 is smaller than 6.

1,3,5,6|7,8,2,4 We make the same process.

1,3,5,6,7|8,2,4 There is no change because number already bigger.

1,3,5,6,7,8|2,4 Now we have to change the 2 order, 1,3,5,6,7|2,8,4 still we have to change the 2 order because smaller than the other items. We make this process until the find right location.

1,2,3,5,6,7,8|4 We change the 4 location like in the changing the 2 location. Same process.

**C Codes**;

#include<stdio.h> void insertionSort(int array[],int size){ for(int i=1;i<size;i++){ int temp = array[i]; int j = i-1; while(j>=0 && temp<array[j]){ array[j+1] = array[j]; j -=1; } array[j+1] = temp; } } void maxToMin(int array[],int size){ for(int i =1;i<size;i++){ int temp = array[i]; int j = i-1; while(j>=0 && temp>array[j]){ array[j+1] = array[j]; j = j-1; } array[j+1]=temp; } } int main(){ int array[] = {3,1,6,5,7,8,2,4}; int size = sizeof(array)/sizeof(array[0]); insertionSort(array,size); printf("Insertion Sort\n"); for(int i=0;i<size;i++){ printf("%d ",array[i]); } maxToMin(array,size); printf("\nMax to Min\n"); for(int i=0;i<size;i++){ printf("%d ",array[i]); } }

**Python Codes** :

def maxtomin(array): for i in range(1,len(array)): temp = array[i] j = i-1 while j>=0 and temp>array[j]: array[j+1] = array[j] j= j-1 array[j+1] = temp array = [3,1,6,5,7,8,2,4] for i in range(1,len(array)): temp = array[i] j = i-1 while j>=0 and temp<array[j]: array[j+1] = array[j] j = j-1 array[j+1] = temp print("Insertion Sort") for i in range(len(array)): print("%d " %array[i]) maxtomin(array) print("Max to Min") for i in range(len(array)): print("%d" %array[i])