Search This Blog

Simplicity is the ultimate sophistication.” — Leonardo da Vinci
Contact me: sreramk360@gmail.com

Sunday, 19 April 2015

Determine the average run-time of insertion sort algorithm



Insertion sorting algorithm analysis
 This article shows the analysis of insertion sorting algorithm and a program to implement insertion sorting algorithm. Link list implementation is used for the implementation.

This algorithm does comparison based sorting which involves $N^2$ iterations for the worse case and $N$ iterations if the list is already in sorted order. For the reader's convenience, a quick description of the algorithm is provided here.  

Let there be an unsorted list $L$ which has its elements read linearly, starting from one of its edges. Another list $L'$ (which is assumed to be always sorted)  is generated upon reading the first element from the list $L$. For each element read from $L$ (let's consider the variable $x$ to store the read value) it's inserted into the sorted list $L'$ in such a position that $L'$ remains sorted  after the insertion (note that initially $L'$ was empty). The position in $L'$ to which the variable $x$ has to be inserted is determined by a linear search through $L'$ starting from one of its edges and comparing the arithmetic priority of $x$ with the succeeding element.

This algorithm explains what basically happens in an insertion sorting algorithm. But it states that the searching process could begin from either of the ends. On the whole, this wouldn't have any influence in the run time, but certain parameters change. For example, if the algorithm is made to arrange a set of numbers in ascending order, and the search iterations begins with the beginning of the list $L'$ during any point in time, then passing on a list that has its elements arranged in descending order takes $O(1)$ to be sorted in acceding order whereas passing on a list which is initially in acceding order would take $O(N^2)$ time to get sorted. Searching from the beginning of the list $L'$ and moving to its end is same as another algorithm which reverses the order of elements in $L$ and then sorts them in ascending order but have its search iteration start from the last element in list $L'$ and move towards the first. So minor changes such as these are not going to count, especially if we do pure theoretical analysis on this topic, rather than provide an optimal practical working modal.

A link to inserting sorting implementation C program.      

Featured post

Why complicating matters is not good

“ Simplicity is the ultimate sophistication.” — Leonardo da Vinci Why is complicating things wrong ? - K Sr...