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<iostream>
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<size;i++)
   {
    cin>>arr[i];
   }

  insertionsort(arr,size);

  cout<<"The elements of array in sorted order are:\n";

  for(i=0;i<size;i++)
  {
   cout<<arr[i]<<"\t";
  }

  cout<<"\n";
 }
  
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.

No comments:

Post a comment