# Tag Archives: bangladesh

## Sorting Algorithm : Insertion Sort

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:

Implemented Code in C:

Output:

Here ary[] means array 🙂

Simulation:(Wikipedia)

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

GeeksForGeeks Algo Implement(Not Worked Yet):

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

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

## C code for bisection method

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:

Algorithm:

1. Start
2. 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*
3. Compute: f1 = f(a1) and f3 = f(b1)
4. If (f1*f3) > 0, then display initial guesses are wrong and goto step 11
Otherwise continue.
5. root = (a1 + b1)/2
6. 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
7. Else, f2 = f(root)
8. If (f1*f2) < 0, then b1=root
9. Else if (f2*f3)<0 then a1=root
10. else goto step 5
*Now the loop continues with new values.*
11. Stop

Output:

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

Output:

## C code for bisection method

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:

Algorithm:

1. Start
2. 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*
3. Compute: f1 = f(a1) and f3 = f(b1)
4. If (f1*f3) > 0, then display initial guesses are wrong and goto step 11
Otherwise continue.
5. root = (a1 + b1)/2
6. 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
7. Else, f2 = f(root)
8. If (f1*f2) < 0, then b1=root
9. Else if (f2*f3)<0 then a1=root
10. else goto step 5
*Now the loop continues with new values.*
11. Stop

Output:

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

Output:

## C code for bisection method

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:

Algorithm:

1. Start
2. 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*
3. Compute: f1 = f(a1) and f3 = f(b1)
4. If (f1*f3) > 0, then display initial guesses are wrong and goto step 11
Otherwise continue.
5. root = (a1 + b1)/2
6. 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
7. Else, f2 = f(root)
8. If (f1*f2) < 0, then b1=root
9. Else if (f2*f3)<0 then a1=root
10. else goto step 5
*Now the loop continues with new values.*
11. Stop

Output:

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

Output:

## C code for bisection method

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:

Algorithm:

1. Start
2. 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*
3. Compute: f1 = f(a1) and f3 = f(b1)
4. If (f1*f3) > 0, then display initial guesses are wrong and goto step 11
Otherwise continue.
5. root = (a1 + b1)/2
6. 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
7. Else, f2 = f(root)
8. If (f1*f2) < 0, then b1=root
9. Else if (f2*f3)<0 then a1=root
10. else goto step 5
*Now the loop continues with new values.*
11. Stop

Output:

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

Output: