Insertion_Sort.cpp

// C++ Program for Insertion Sort.
#include<bits/stdc++.h>
using namespace std;

//Function to Sort an Array using Insertion Sort
void insertionSort(int arr[],int n)
{
    int i, key, j;
    for(i = 1; i < n; i++)
    {
        key = arr[i];
        j = i - 1;
        //Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position
        while(j>=0 && arr[j] > key)
        {
            arr[j+1] = arr[j];
            j = j-1;
        }
        arr[j+1] = key;
    }
}

//A Utility function to print an array of size n
void printArray(int arr[], int n)
{
    int i;
    for(i=0;i<n;i++)
        cout<< arr[i] << " ";
    cout<< endl;
}

//Driver Code
int main()
{
    int arr[] = {12,11,13,5,6,27};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<< "Sorted Array:\n";
    insertionSort(arr,n);
    printArray(arr,n);
    return 0;
}