Insertion sort

The sorting problem
Input: Array of numbers , unsorted. Eg.

Output : Same numbers sorted in some order, say increasing order. Eg.

Insertion sort:
An efficient elementary sort method which places each element in it's proper place among the elements which are already placed

Pseudocode for selection sort

• Starts by considering the first two elements of the array data, if out of order, swap them 
• Consider the third element, insert it into the proper position among the first three elements. 
• Consider the forth element, insert it into the proper

Example
Consider the following array:

We have to sort the array in increasing order. So, first we take first 2 elements i.e. 28 and 18 and swap them as they are out of order.

2nd pass - Now, we consider first 3 elements. As, 7 is smallest element, we bring it in 0th index, and shift the rest of the elements from there on, as they are already sorted. So, the idea is to exchange the element selected in this pass (here 7) to swap with all elements in the left which are higher than that element.

Likewise, the algorithm goes on.

Pseudocode

public static void sort(int[] array)
{
    int N = array.length;
    for(int i=0;i < N;i++)
        for(int j=0;j>0;j--)
            if(a[j] < a[j-1])
                swap(a[j],a[j-1]);
            else
                break;
}

Implementation in cpp

Implementation in cpp using templates

#include <iostream>
#include <string.h>

template <typename T>
class InsertionSort
{
    public:
        InsertionSort();
        ~InsertionSort();

        void sort(T arr[], int size);
    private:
        void compareExchange(T arr[], int l, int r);
        bool greater(T left, T right);
};

//Constructor
template <typename T>
InsertionSort<T>::InsertionSort(){}

//Destructor
template <typename T>
InsertionSort<T>::~InsertionSort(){}

template <typename T>
void InsertionSort<T>::sort(T arr[], int size)
{
    for(int i = 1; i < size; ++i)
    {
        for(int j = i; j > 0; --j)
        {
            compareExchange(arr, j-1, j);
        }
    }
}

template <typename T>
void InsertionSort<T>::compareExchange(T arr[], int l, int r)
{
    if(greater(arr[l], arr[r]))
    {
        T temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }
}

template <typename T>
bool InsertionSort<T>::greater(T left, T right)
{
    return left > right;
}

template <>
bool InsertionSort<const char*>::greater(const char *left, const char *right)
{
    return strcmp(left, right) > 0;
}

template <typename T>
void print(T arr[], int size)
{
    for(int i = 0; i < size; ++i)
        std::cout << arr[i] << " ";
    std::cout << std::endl;
}

template <>
void print(std::string arr[], int size)
{
    for(int i = 0; i < size; ++i)
        std::cout << arr[i].c_str() << " ";
    std::cout << std::endl;
}

template <>
void print(const char *ptrArray, int size)
{
    for(int i = 0; i < size; ++i)
        std::cout << ptrArray[i] << " ";
    std::cout << std::endl;
}

int main()
{
    int arr[] = { 10, 65, 35, 25, 15, 75, 85, 45, 65 };
    InsertionSort<int> isInt;
    isInt.sort(arr, 9);
    print(arr, 9);

    std::string strArr[] = { "pankaj", "paresh", "hello", "world", "ankit", "aditya", "sankalp", "aladdin" };
    InsertionSort<std::string> isString;
    isString.sort(strArr, 8);
    print(strArr, 8);

    const char* ptrArray[] = { "pankaj", "paresh", "hello", "world", "ankit", "aditya", "sankalp", "aladdin", "george"};
    InsertionSort<const char*> isPtr;
    isPtr.sort(ptrArray, 9);
    print(ptrArray, 9);

    return 0;
}

Implementation in java using generics

 import org.junit.Assert;
 import org.junit.Test;
 
 class GenericInsertionSorter
 {
     public <T extends Comparable<T>> void sort(T[] elems) {
         int size = elems.length;
 
         for (int outerLoopIdx = 1; outerLoopIdx < size; ++outerLoopIdx) {
             for (int innerLoopIdx = outerLoopIdx; innerLoopIdx > 0; --innerLoopIdx) {
                 if (elems[innerLoopIdx - 1].compareTo(elems[innerLoopIdx]) > 0) {
                     T temp = elems[innerLoopIdx - 1];
                     elems[innerLoopIdx - 1] = elems[innerLoopIdx];
                     elems[innerLoopIdx] = temp;
                 }
             }
         }
     }
 }
 
 public class InsertionSortTester
 {
     private String[] unsortedNames = new String[] {
             "Pankaj",
             "Paresh",
             "Ankit",
             "Sankalp",
             "Aditya",
             "Prem",
             "Rocket",
             "Singh",
             "Alabama",
             "Alaska",
             "Animal" };
 
     private String[] sortedNames = new String[] {
             "Aditya",
             "Alabama",
             "Alaska",
             "Animal",
             "Ankit",
             "Pankaj",
             "Paresh",
             "Prem",
             "Rocket",
             "Sankalp",
             "Singh" };
 
     @Test
     public void testStringSort() {
         GenericInsertionSorter ss = new GenericInsertionSorter();
         ss.sort(unsortedNames);
         Assert.assertArrayEquals(unsortedNames, sortedNames);
     }
 }