Insertion Sort ( C & Python 3 )

Insertion Sort 
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands. 

Consider you have 10 cards out of a deck of cards in your hand. And they are sorted, or arranged in the ascending order of their numbers.

If I give you another card, and ask you to insert the card in just the right position, so that the cards in your hand are still sorted. What will you do?

Well, you will have to go through each card from the starting or the back and find the right position for the new card, comparing it's value with each card. Once you find the right position, you will insert the card there.

Similarly, if more new cards are provided to you, you can easily repeat the same process and insert the new cards and keep the cards sorted too.

This is exactly how insertion sort works. It starts from the index 1(not 0), and each index starting from index 1 is like a new card, that you have to place at the right position in the sorted sub-array on the left.

Following are some of the important characteristics of Insertion Sort:

1. It is efficient for smaller data sets, but very inefficient for larger lists.
2. Insertion Sort is adaptive, that means it reduces its total number of steps if a partially sorted array is provided as input, making it efficient.
3. It is better than Selection Sort and Bubble Sort algorithms.
4. Its space complexity is less. Like bubble Sort, insertion sort also requires a single additional memory space.
5. It is a stable sorting technique, as it does not change the relative order of elements which are equal.

Below, we have a pictorial representation of how bubble sort will sort the given array.

Implementing Insertion Sort Algorithm

A program involving insertion sort in C

/*
Sorting using insertion sort method
@uther - Abhishek
*/

#include <stdio.h>

int* insertion_sort(int* ,int );
int main()
{
    int n,i,*sorted_array;
    printf("\nEnter the number of items in the array  : ");
    scanf("%d",&n);
    int array[n];
    for(i=0;i<n;i++)
    {
        printf("\nEnter element %d : ",i+1);
        scanf("%d",&array[i]);
    }
    sorted_array=insertion_sort(array,n);
    for(i=0;i<n;i++)
    {
        printf(" %d",sorted_array[i]);
    }
    return 0;
}

int* insertion_sort(int *array,int n)
{
    int temp,i,j;
    for(i=1;i<n;i++)
    {
        temp=array[i];
        j=i-1;
        while(j>=0 && array[j]>temp)
        {
            array[j+1]=array[j];
            j--;
        }
        array[j+1]=temp;
    }
    return array;
}

A program involving insertion sort in Python 3

'''
Sorting by Insertion Sort
@uther- Abhishek 
'''

def insertion_sort(array):
    for i in range(1,len(array)):
        j=i-1
        temp=array[i]
        while(j>=0 and array[j]>temp):
            array[j+1]=array[j]
            j=j-1
        array[j+1]=temp
    return array
    

array=list(int(x) for x in input().split())
sorted_array=insertion_sort(array)
print(sorted_array)

Insertion sorting in Java to be out soon.