Sorting Algorithm : Insertion Sort

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

Pseudocode:

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:

#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;
}

Output:

Here ary[] means array 🙂

Simulation:(Wikipedia)

Harvard CS50 course:
http://cs50.tv/2016/fall/

GeeksForGeeks Algo Implement(Not Worked Yet):

#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):

#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:

http://www.geeksforgeeks.org/time-complexity-insertion-sort-inversions/
For some theory revise this video is good:
https://www.youtube.com/watch?v=olaM9mqOmlI