## Thursday 9 November 2017

### Insertion Sort in C++

In this post, we will see implementation of insertion sort in C++ language.

Time Complexity of Insertion Sort is O(n2) where n is the total number of elements in the input array.

Program (insertionsort.cpp)
 #include using namespace std; //insertion sort void insertionsort(int arr[], int size) {    int i, key, j;    for (i = 1; i < size; i++)    {        key = arr[i];        j = i-1;                 while (j >= 0 && arr[j] > key)        {            arr[j+1] = arr[j];            j = j-1;        }        arr[j+1] = key;    } } //main() function int main()  {   int arr[10],size,i,j,index,choice;   cout<<"Enter total number of elements of array\n";   cin>>size;   cout<<"Enter the elements of array\n";   for(i=0;i>arr[i];    }   insertionsort(arr,size);   cout<<"The elements of array in sorted order are:\n";   for(i=0;i

Output:
 parag@parag-Inspiron-N4010:~/Desktop/programs\$ g++ insertionsort.cpp parag@parag-Inspiron-N4010:~/Desktop/programs\$ ./a.out Enter total number of elements of array 7 Enter the elements of array 23 11 45 26 99 34 57 The elements of array in sorted order are: 11 23 26 34 45 57 99

Check other posts on Data Structures in this link http://www.comrevo.com/2016/09/data-structures.html.