From this two video I tried to re learn and implement the algorithm with pseudo code.

https://www.youtube.com/watch?v=i-SKeOcBwko

**Pseudocode:**

1 2 3 4 5 6 7 8 9 10 11 12 |
InsertionSort(A,n) for i=1 to Array.length(n) do key=A[i] j=i-1 while( j>=0 and A[j]>key ) do A[j+1]=A[j] j=j-1 done A[j+1]=key done |

Implemented Code in C:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include<stdio.h> int main() { int i,j,n,key,ary[30]; printf("Enter total elements:"); scanf("%d",&n); printf("Enter %d elements: ",n); for(i=0;i<n;i++){ scanf("%d",&ary[i]); } //Ascending order for(i=1;i<n;i++) { key=ary[i]; j=i-1; while((j>=0)&&(ary[j]>key)){ ary[j+1]=ary[j]; j=j-1; } ary[j+1]=key; } printf("After Sorting Ascending Order: "); for(i=0;i<n;i++) { printf(" %d",ary[i]); } //Descending Order for(i=1;i<n;i++) { key=ary[i]; j=i-1; while((j>=0)&&(ary[j]<key)){ ary[j+1]=ary[j]; j=j-1; } ary[j+1]=key; } printf("\nAfter Sorting Descending Order: "); for(i=0;i<n;i++) { printf(" %d",ary[i]); } return 0; } |

Here ary[] means array 🙂

Simulation:(Wikipedia)

Harvard CS50 course:

http://cs50.tv/2016/fall/

GeeksForGeeks Algo Implement(Not Worked Yet):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include<cstdio> #include<iostream> using namespace std; void insertionSort(int arr[], int n){ int i,key,j; for(i=1; i<=n; 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; } } void printInsertion(int arr[],int n){ int i; for(i=0;i<n;i++) { cout<<arr[i]<<endl; } } int main(){ int arr[101]; int n=sizeof(arr)/sizeof(arr[0]); for(int i=0; i<=n; i++){ cin>>arr[n]; } insertionSort(arr, n); printInsertion(arr, n); return 0; } |

http://quiz.geeksforgeeks.org/insertion-sort/

Practice Problem:

http://www.practice.geeksforgeeks.org/problem-page.php?pid=700148

https://www.hackerearth.com/practice/algorithms/sorting/insertion-sort/practice-problems/

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_A

CLRS Theory:

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/insertionSort.htm

Simple Implementation of Insertion Sorting(Idea Sanfoundry):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include<cstdio> #include<iostream> using namespace std; int main(){ int a[101]; int n,i,j,p,key; cin>>n; for(p=0;p<n;p++) { cin>>a[p]; } for(i=0; i<n; i++){ key=a[i]; j=i-1; while(j>=0 && a[j]>key){ a[j+1]=a[j]; j=j-1; } a[j+1]=key; } for(p=0;p<n;p++){ cout<<" "<<a[p]<<endl;; } return 0; } |

It is helpful: http://www.sanfoundry.com/cpp-program-sort-array/

### Time complexity of Insertion Sort:

- Worst case complexity : O(n^2)
- Best case complexity : O(n)
- Average case complextiy: O(n^2)Reference:

http://bigocheatsheet.com/

How to calculate complexity there is a example available at the upper video “Lecture 7”

and there are some links

http://stackoverflow.com/questions/19827193/time-complexity-of-insertion-sort

Here a good presentation about this sorting

http://www.cs.mcgill.ca/~cs203/lectures/lecture7/sld006.htm

Reference: http://www.cquestions.com/2009/09/insertion-sort-algorithm.html

For descending order I took help from:

http://cboard.cprogramming.com/c-programming/73433-sorting-descending-order.html

Here they change the comparison value for descending at while loop condition

Another good website:

Time complexity of insertion sort when there are O(n) inversions?

For some theory revise this video is good:

https://www.youtube.com/watch?v=olaM9mqOmlI