C++ program for insertion sort algorithm
Description:
insertion sort algorithm is simple sorting algorithm. it is less efficient for large number of data compare to heap sort, quick sort, merge sort.
insertion sort algorithm is simple sorting algorithm. it is less efficient for large number of data compare to heap sort, quick sort, merge sort.
this algorithm picks one elements at a time and insert the element at location belongs to sorted list and repeats until no input elements remain unsorted.
Time complexity is O(n*2) in average case and worst case and O(n) in best case(All elements are already sorted).
LOGIC:
LOOP from i = second element of list to last element
pick element array[i] and insert it into sorted list array[0...i-1].
C++ code:
#include<iostream> using namespace std; void insertion_sort(int[], int); void print_list(int[], int); void insertion_sort(int arr[], int n) { int i,j,key; for(i=1;i<n;i++) { key=arr[i]; for(j=i-1;j>=0 && key<arr[j];j--) arr [j + 1 ] = arr [j]; arr[j+1]=key; } } void print_list(int arr[], int n) { for(int i=0;i<n;i++) cout<<arr[i]<<" "; } int main() { int arr[]={25,15,12,45,6,35,26,13}; insertion_sort(arr,8); print_list(arr,8); return 0; }
input: 25,15,12,45,6,35,26,13
Output: 6 12 13 15 25 26 35 45
Comments