Insertion Sort In C++

Insertion Sort Program in C++

Insertion Sort:  In this Method, the element is inserted at its proper position in the sorted list. In this method initially the whole list is divided into two parts,one part containing the first element and the second containing the other elements. The first Part is called the sorted list and the second part is called the unsorted list. In other words we have to divide the list into two parts. sorted list and unsorted list. We start with the first element of unsorted list (the second element of the list) and insert it into its proper position in the sorted list.

#include<iostream>
using namespace std;

template <class T>
void read(T a[], int n) {
    for(int i=0;i<n;i++) {
        cout<<"Enter elements:";
        cin>>a[i];
    }
}

template <class T>
void display(T a[], int n) {
    for(int i=0;i<n;i++) {
        cout<<" "<<a[i];
    }
}


template <class T>
void sort(T a[], int n) {
    int j;
    for(int i=1;i<n;i++) {
        T temp = a[i];
        for(j=i-1;j>=0 && a[j]>temp;j--) {
            a[j+1] = a[j];

        }
a[j+1] = temp;
    }
}


int main() {
    int arr[20],size;
    cout<<"Enter the size of the array:";
    cin>>size;
    read(arr,size);
    display(arr,size);
    sort(arr,size);
    cout<<"after sorting"<<endl;
    display(arr,size);
}