Insertion Sort

Insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there in each iteration. It repeats until no input elements remain. It always maintains a sorted sub list in the lower position of the list.

Time Complexity of this algorithm is O(n*n)

Insertion sort takes maximum time to sort if elements are sorted in reverse order. And it takes minimum time (Order of n) when elements are already sorted. Normally this algorithm is used when number of elements is small. It can also be useful when input array is almost sorted, only few elements are misplaced.

      Binary search can reduce the number of comparisons in normal insertion sort. We can use Binary search due to find the proper location to insert the selected item of each iteration. At normal insertion, sort takes O(i) in worst case but it will take O(log i) by using binary search.

Algorithm
insertionSort(arr, n)   // Sort an arr[] of size n
Loop from i = 1 to n-1.
……a) Pick element arr[i] and insert it into sorted sequence arr[0…i-1]

Bellow figure shows the insertion sort process. The shaded items will represent the order of each iteration.

Here bellow is another figure will show details process of a single iteration.

[Problem] 

Sort the given data in ascending order by using Insertion sort. 

The maximum size of the data is 100. Duplicated input may exist. 

[Input] 

The first input line contains the number of test cases, T. 

The next line contains the number of input data. 

Next, the integer data will be listed 

[Output] 

For each given test case, print the sorted list. 

 INPUT                                                   

=============                                                   

1 // number of Test cases 

5 // Test case index 

1 4 5 2 3

OUTPUT 

===============================

#1 1 2 3 4 5

C++ Solution:

#include <stdio.h>
#include<iostream>
using namespace std;

long long factorial(int num);

int main(void)
{
    int test_case;
    int T;
    int num;
    long long value;

    freopen("recursionInput.txt", "r", stdin);
    cin >> T;
    for (test_case = 1; test_case <= T; ++test_case)
    {
        scanf("%d", &num);
        value = factorial(num);
        printf("#%d %d! = %lld\n", test_case, num, value);
    }
}

long long factorial(int num)
{
    if (num == 0)
    {
        return 1;
    }
    else
    {
        return num * factorial(num - 1);
    }
}

Java Solution:

package com.algorithm;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class InsertionSort {

    static private final String INPUT = System.getProperty("user.dir") + "\\src\\data\\insertionInput.txt";
    static Scanner sc;
    static int inputData[];
    static int num;


    public static void main(String[] args) {
        FileInputStream instream = null;
        try {
            instream = new FileInputStream(INPUT);
            System.setIn(instream);
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }

        sc = new Scanner(System.in);

        int T = sc.nextInt();

        for (int test_case = 1; test_case <= T; test_case++)
        {
            num = sc.nextInt();

            inputData = new int[num];           
            for (int i = 0; i < num; i++)
            {
                inputData[i] = sc.nextInt();
            }

            insertionSort();

            System.out.print("#" + test_case + " ");
            printResult();
        }

        sc.close();

    }

    static void insertionSort()
    {
        for (int i = 1; i < num; i++)
        {
            int temp = inputData[i];
            int j = i - 1;

            while ((temp < inputData[j]) && (j >= 0))
            {
                inputData[j + 1] = inputData[j];
                j = j - 1;
            }
            inputData[j + 1] = temp;
        }
    }

    static void printResult()
    {
        int i;

        for (i = 0; i < num; ++i)
        {
            System.out.print(inputData[i] + " ");
        }
        System.out.println();
    }
}