Tag Archives: bangladesh

What Bodybuilders See ! :D

12310588_951071261632290_2364433213835219961_n

Sorting Algorithm : Insertion Sort

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

Pseudocode:

Implemented Code in C:

Output:
2015-08-07 13_30_30-C__Users_User_Desktop_insertionsort.exe

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:

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:

2014-11-09 03_03_31-

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

Output:2014-11-27 12_22_54-