Tag: bangladesh

Tag Archives: bangladesh

Sorting Algorithm : Insertion Sort

Posted on August 7, 2015 | Leave a comment

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

InsertionSort(A,n)

for i=1 to Array.length(n) do

key=A[i]

j=i-1

while( j>=0 and A[j]>key )

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

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

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

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

C code for bisection method

Posted on November 23, 2014 | Leave a comment

The Bisection Method is a numerical method for estimating the roots of a polynomial f(x). It is one of the simplest and most reliable but it is not the fastest method.

Problem: Here we have to find root for the polynomial x^3+x^2-1

Solution in C:

#include<stdio.h>
#include<math.h>
#define TOL 0.0001
float func(double x)
{
return (pow(x,3)+pow(x,2)-1);
}

int main()
{
    double a,b;
    int iteration,i;
printf("Root finding of function x^3+x^2-1 using bisection method.\n");
printf("Enter the first approximation of the root:\n");
scanf("%lf",&a);

printf("Enter the second approximation of the root:\n");
scanf("%lf",&b);

printf("Enter the iteration you want to perform :");
scanf("%d",&iteration);
i=1;
double a1=a;
double b1=b;
double root,f1,f2,f3;
if(func(a1)==0)
    root=a1;
else if(func(b1)==0)
    root=b1;
else{
while(i<iteration)
{
    root=(a1+b1)/2;

f1=func(a1);
f2=func(root);
f3=func(b1);
if(f2==0)
{
    root=f2;
    break;
}
printf("The root after %d iteration is %lf\n",i,root);
if(f1*f2<0)
b1=root;
else
    if(f2*f3<0)
    a1=root;
i++;
}
}
printf("The approximation of the root is %lf",root);
    return 0;
}

#include<stdio.h>

#include<math.h>

#define TOL 0.0001

float func(double x)

{

return (pow(x,3)+pow(x,2)-1);

}

int main()

{

double a,b;

int iteration,i;

printf("Root finding of function x^3+x^2-1 using bisection method.\n");

printf("Enter the first approximation of the root:\n");

scanf("%lf",&a);

printf("Enter the second approximation of the root:\n");

scanf("%lf",&b);

printf("Enter the iteration you want to perform :");

scanf("%d",&iteration);

i=1;

double a1=a;

double b1=b;

double root,f1,f2,f3;

if(func(a1)==0)

root=a1;

else if(func(b1)==0)

root=b1;

else{

while(i<iteration)

{

root=(a1+b1)/2;

f1=func(a1);

f2=func(root);

f3=func(b1);

if(f2==0)

{

root=f2;

break;

}

printf("The root after %d iteration is %lf\n",i,root);

if(f1*f2<0)

b1=root;

else

if(f2*f3<0)

a1=root;

i++;

}

printf("The approximation of the root is %lf",root);

return 0;

}

Algorithm:

Start
Read a1, b1, TOL
*Here a1 and b1 are initial guesses
TOL is the absolute error or tolerance i.e. the desired degree of accuracy*
Compute: f1 = f(a1) and f3 = f(b1)
If (f1*f3) > 0, then display initial guesses are wrong and goto step 11
Otherwise continue.
root = (a1 + b1)/2
If [ (a1 – b1)/root ] < TOL , then display root and goto step 11
* Here [ ] refers to the modulus sign. *
or f(root)=0 then display root
Else, f2 = f(root)
If (f1*f2) < 0, then b1=root
Else if (f2*f3)<0 then a1=root
else goto step 5
*Now the loop continues with new values.*
Stop

Output:

Another Problem Solving Code:
Problem: Here we have to find root for the polynomial x^3+x^2-1 upto 4D

#include<stdio.h>
#include<math.h>
#define f(y)  (pow(x,3)+x*x-1);
int main()
{
    double a,b,m=-1,x,y;
    int n=0,k,i;
    printf("Enter the value of a: ");
    scanf("%lf",&a);
    printf("Enter the value of b: ");
    scanf("%lf",&b);
    printf("How many itteration you want: ");
   scanf("%d",&k);
   printf("\n n      a         b        xn=a+b/2       sign of(xn)\n");
   printf("-------------------------------------------------------------\n");
   for(i=1;i<=k;i++)
   {
        x=(a+b)/2;
        y=f(x);
        if(m==x)
        {
            break;
        }
        if(y>=0)
        {
             printf(" %d    %.5lf     %.5lf    %.5lf       +\n",i,a,b,x);
            b=x;
        }
        else if(y<0)
        {
             printf(" %d    %.5lf     %.5lf    %.5lf       -\n",i,a,b,x);
            a=x;
        }
         m=x;
   }
    printf("\nThe approximation to the root is %.4lf which is upto 4D",b);

    return 0;
}

#include<stdio.h>

#include<math.h>

#define f(y) (pow(x,3)+x*x-1);

int main()

{

double a,b,m=-1,x,y;

int n=0,k,i;

printf("Enter the value of a: ");

scanf("%lf",&a);

printf("Enter the value of b: ");

scanf("%lf",&b);

printf("How many itteration you want: ");

scanf("%d",&k);

printf("\n n a b xn=a+b/2 sign of(xn)\n");

printf("-------------------------------------------------------------\n");

for(i=1;i<=k;i++)

{

x=(a+b)/2;

y=f(x);

if(m==x)

{

break;

}

if(y>=0)

{

printf(" %d %.5lf %.5lf %.5lf +\n",i,a,b,x);

b=x;

}

else if(y<0)

{

printf(" %d %.5lf %.5lf %.5lf -\n",i,a,b,x);

a=x;

}

m=x;

}

printf("\nThe approximation to the root is %.4lf which is upto 4D",b);

return 0;

}

Output:

Tag Archives: bangladesh

What Bodybuilders See ! :D

Sorting Algorithm : Insertion Sort

Time complexity of Insertion Sort:

C code for bisection method

Caution and Tips:

Category

About Me & MyBlog

Recent Posts

Recent Comments

My Facebook

My Algorithmic Progress in OJ’s

My Github

My Linkedin

Count per Day

Archives

This site is powered by:

Bookmarks

My Coding Page

Top Posts & Pages

My Skills

My Poster/Presentations

My Videos

My Bookshelf

Quote From Life

Tag Archives: bangladesh

What Bodybuilders See ! :D

Sorting Algorithm : Insertion Sort

Time complexity of Insertion Sort:

C code for bisection method

Caution and Tips:

Category

About Me & MyBlog

Recent Posts

Recent Comments

My Facebook

My Algorithmic Progress in OJ’s

My Github

My Linkedin

Tags

Count per Day

Archives

This site is powered by:

Bookmarks

My Coding Page

Top Posts & Pages

My Skills

My Poster/Presentations

My Videos

My Bookshelf

Quote From Life