Insertion sort

Insertion sort is an elementary sorting algorithm. It has a time complexity of Θ(n²), thus being slower than heapsort, merge sort and also shellsort. Insertion sort is well suited for sorting small data sets or for the insertion of new elements into a sorted sequence.

Idea

Let a₀, ..., a_n-1 be the sequence to be sorted. At the beginning and after each iteration of the algorithm the sequence consists of two parts: the first part a₀, ..., a_i-1 is already sorted, the second part a_i, ..., a_n-1 is still unsorted (i  0, ..., n).

In order to insert element a_i into the sorted part, it is compared with a_i-1, a_i-2 etc. When an element a_j with a_ja_i is found, a_i is inserted behind it. If no such element is found, then a_i is inserted at the beginning of the sequence.

After inserting element a_i the length of the sorted part has increased by one. In the next iteration, a_i+1 is inserted into the sorted part etc. While at the beginning the sorted part consists of element a₀ only, at the end it consists of all elements a₀, ..., a_n-1.

Example:  The following table shows the steps for sorting the sequence 5 7 0 3 4 2 6 1. On the left side the sorted part of the sequence is shown in red. For each iteration, the number of positions the inserted element has moved is shown in brackets. Altogether this amounts to 17 steps.

5	7	0	3	4	2	6	1		(0)
5	7	0	3	4	2	6	1		(0)
0	5	7	3	4	2	6	1		(2)
0	3	5	7	4	2	6	1		(2)
0	3	4	5	7	2	6	1		(2)
0	2	3	4	5	7	6	1		(4)
0	2	3	4	5	6	7	1		(1)
0	1	2	3	4	5	6	7		(6)

Implementation

The following simulation illustrates the realization of the algorithm. The corresponding program is given subsequently.

Simulation of insertion sort

The following function insertionsort sorts an integer array a[0], ..., a[n-1].

The sorting function is encapsulated in a class InsertionSorter. The method sort passes the array to be sorted to an array a, sets n to its length and calls insertionsort.

The statement to sort an array b with insertion sort is

InsertionSorter.sort(b);

The program follows.

public class InsertionSorter { private static int[] a; private static int n; public static void sort(int[] a0) { a=a0; n=a.length; insertionsort(); } private static void insertionsort() { int i, j, t; for (i=1; i<n; i++) { j=i; t=a[j]; while (j>0 && a[j-1]>t) { a[j]=a[j-1]; j--; } a[j]=t; } } } // end class InsertionSorter

Analysis

The worst case occurs when in every step the proper position for the element that is inserted is found at the beginning of the sorted part of the sequence. I.e. in the while-loop sequences of length 1, 2, 3, ..., n-1 are scanned. Altogether, these are (n-1)·n / 2    Θ(n²) operations. This case occurs when the original sequence is sorted in decreasing order.

It is possible to find the inserting position of element a_i faster, namely by binary search. However, moving the elements to the right in order to make room for the element to be inserted takes linear time anyway.

The exact number of steps required by insertion sort is given by the number of inversions of the sequence.

Definition:  Let a  =  a₀, ..., a_n-1 be a finite sequence. An inversion is a pair of index positions, where the elements of the sequence are out of order. Formally, an inversion is a pair (i, j), where i < j and a_i > a_j.¹)

Example:  Let a = 5, 7, 4, 9, 7. Then, (0, 2) is an inversion, since a₀ > a₂, namely 5 > 4. Also, (1, 2) is an inversion, since 7 > 4, and (3, 4) is an inversion, since 9 > 7. There are no other inversions in this sequence.

We now count the inversions (i, j) of a sequence a separately for each position j. The resulting value of v_j gives the number of elements a_i to the left of a_j which are greater than a_j.

For instance, for the sequence a = 5, 7, 4, 9, 7 we have v₂ = 2, since the two inversions (0, 2) and (1, 2) have 2 as their second component. Here, 5 and 7 are greater than 4.

Definition:  The inversion sequence v = v₀, ..., v_n-1 of a sequence a = a₀, ..., a_n-1 is defined by

v_j  =  |{ (i, j)  |  i < j      a_i > a_j }|

for j = 0, ..., n-1.

Example:  The above sequence a = 5, 7, 4, 9, 7 has the inversion sequence v = 0, 0, 2, 0, 1.

Obviously, we have v_ii for all i = 0, ..., n-1. If all v_i are 0, then and only then the sequence a is sorted. If the sequence a is a permutation, then it is uniquely determined by its inversion sequence v. The permutation n-1, ..., 0 has inversion sequence 0, ..., n-1.

Theorem:  Let a  =  a₀, ..., a_n-1 be a sequence and v  =  v₀, ..., v_n-1 be its inversion sequence. Then the number of steps T(a) required by insertion sort to sort sequence a is

T(a)  =    _{i = 0, ..., n-1}  v_i

Proof:  Obviously, insertion sort takes v_i steps in each iteration i. Thus, the overall number of steps is equal to the sum of all v_i.

Example:  The following table shows the sequence a of the first example and its corresponding inversion sequence. For instance,v₅ = 4 since 4 elements to the left of a₅ = 2 are greater than 2 (namely 5, 7, 3 and 4). The total number of inversions is 17.

i	0	1	2	3	4	5	6	7
ai	5	7	0	3	4	2	6	1
vi	0	0	2	2	2	4	1	6

Thus, insertion sort requires 17 steps to sort this sequence (see first example).

http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/insert/insertionen.htm

http://www.programiz.com/article/insertion-sort-algorithm-programming

C#: Difference between “throw” and “throw ex” in C# .Net Exception

C#: Difference between “throw” and “throw ex” in C# .Net Exception

In day to day development, we all are very familiar with Exception  handling. We pretty much all know that we should wrap the code which may cause for any error in try/catch block and do something about error like give a error message to end user. Here I am not going to explain about Exceptionhandling in C#. Instead I am going to talk about a particular aspect of Exception  handling, which is"throw" vs "throw ex".

You can also find my other articles related to C#, ASP.Net,  jQuery, Java Script and SQL Server. I am writing this post because I was asked this question recently in a interview and unfortunately I didn't  know the answer. So I am posting this for those guys who uses "throw" and "throw ex" frequently but don't know the differences (not all,some knows).

Difference between “throw” and “throw ex”

Take a look on the below code snippest-

throw ex	throw
? 1 2 3 4 5 6 7 8 try {    //Code which fails and raise the error } catch (Exception ex) {    throw ex; }	? 1 2 3 4 5 6 7 8 try {    //Code which fails and raise the error } catch (Exception ex) {    throw; }

Both the codes are perfectly reasonable and does the job. You can not get any difference in both of them until you are trying to debug the code to resolve the issue. That difference is the Stack Trace Information that gets sent with the exception
"When you throw an exception using "throw ex" then you override the original stack trace with a new stack trace that starts from the throwing method."

To understand it more clearly take a look an example for both the cases-
throw ex

---

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

using System; using System.Collections.Generic; using System.Linq; using System.Text;   namespace ConsoleApplication1 {     class Program     {         static void Main(string[] args)         {             try             {                 MethodA();             }             catch (Exception ex)             {                 //Showing overridden exception stack with MethodA instead of MethodB on top                 Console.WriteLine(ex.ToString());             }         }           private static void MethodA()         {             try             {                 MethodB();             }             catch (Exception ex)             {                 //Overrides original stack trace                 throw ex;             }         }           private static void MethodB()         {             throw new NotImplementedException();         }     } }

In the above code you can see that I have called a function "MethodA()" which calls another function"MethodB()". MethodB() raises an exception which is caught by MethodA() andMethodA()throws the exception with Exception object "ex". Now take a look on the output of the above code.

Here you can see that stack string shows the MethodA() instead of MethodB() on the top. Which is not the right function which raised the exception.

Now change the previous code little bit.
throw ex

---

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

using System; using System.Collections.Generic; using System.Linq; using System.Text;   namespace ConsoleApplication1 {     class Program     {         static void Main(string[] args)         {             try             {                 MethodA();             }             catch (Exception ex)             {                 //Showing original exception stack with MethodB on top                 Console.WriteLine(ex.ToString());             }         }           private static void MethodA()         {             try             {                 MethodB();             }             catch (Exception ex)             {                 //Keeps original stack trace                 throw;             }         }           private static void MethodB()         {             throw new NotImplementedException();         }     } }

Now I have replaced "throw ex;" with "throw;" in MethodA().After this change, now take a look on the new output.

Now you can see here, new stack string shows the MethodB() on the top and then MethodA() andMain() method.