CopyPastehas never been so tasty!

Insertion Sort in C#

by anonymous

  • 0
  • 0
  • 0
57 views

Orignal Source:http://codingvilla.com/insertion-sort-csharp-single-article-622.aspx

Insertion Sort

 

Insertion sort is more efficient to use when elements of array are lesser in number or nearly sorted. In insertion sort an element is compared with all previously sorted elements before proceeding to next comparison. It means that if an element contains a small value than it is compared with the entire previous sorted element.

 

 

How Insertion Sort Works

 

To see how insertion sort works, let’s take list of numbers

 

4  1  7  5  6  0  3

 

We examine the second number here 1 is in the list. It is compared with the previously sorted elements. There is only one element which is 4. As 1 <4 so we insert 1 at the index 0 and 4 takes place of the position 1.

 

1  4   7   5   6   0   3

 

Now we examine the next number, 7. As it is > than 1 and 4 so it is already in its correct position.

 

1   4  7  5  6  0  3

 

Now consider number 5, it must be inserted between 4 and 7.

 

 

1      4   5   6   7   0   3

 

The next number is 0 which is to be inserted at the starting index.

 

0     1  4  5  6  7  3

 

 

Finally the last number 3 is considered which is to be inserted in between 1 and 4.

 

 

 

0      1  3  4  5  6  7

 

 

The algorithm for the insertion sort is as follows:

 

 

public static int[] InsertionSort(int[] unsortedarrayed)

        {

 

for (int i = 1; i <unsortedarrayed.Length; i++)

            {

int temp = unsortedarrayed[i];

int j = i - 1;

 

while ((j > -1) && (unsortedarrayed[j] > temp))

                {

 

int temp1 = unsortedarrayed[j + 1];

 

unsortedarrayed[j + 1] = unsortedarrayed[j];

 

unsortedarrayed[j] = temp1;

    j = j - 1;

 

                }

            }

 

returnunsortedarrayed;

        }

 

 

The for loop will go through all the elements of an array, examining each element to find its insertion point. The while loop checks whether the number to be inserted is greater than the previous element. The temp variables are used to store the number to be inserted and the comparable number.

 

Its complexity is O(n2).

 

The following sample code will illustrates the sorting of an array with the help of insertion sort.

 

 

Code

 

 

class Program

    {

static void Main(string[] args)

        {

int i, j;

            int[] unsortedarray = new int[] {4 ,1 ,7 ,5 ,6 ,0 ,3 };

for (i = 0; i <unsortedarray.Length; i++)

            {

Console.WriteLine(unsortedarray[i]);

            }

int[] sortedarray= InsertionSort(unsortedarray);

for (i = 0; i <sortedarray.Length; i++)

            {

Console.WriteLine(sortedarray[i]);

            }

Console.ReadLine();

        }

public static int[] InsertionSort(int[] unsortedarrayed)

        {

for (int i = 1; i <unsortedarrayed.Length; i++)

            {

int temp = unsortedarrayed[i];

int j = i - 1;

while ((j > -1) && (unsortedarrayed[j] > temp))

                {

inttemp1 = unsortedarrayed[j + 1];

unsortedarrayed[j + 1] = unsortedarrayed[j];

unsortedarrayed[j] = temp1;

                    j = j - 1;

                }

            }

returnunsortedarrayed;

        }

    }

Add A Comment: