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