##
Insertion Sort
*June 10, 2008*

*Posted by Thinker in Algorithms.*

Tags: Algorithms, CLR, Insertion Sort

add a comment

Tags: Algorithms, CLR, Insertion Sort

add a comment

I wanted to write on Algorithms for a long time and here i got a chance to write on them; Today I am going to post on Insertion sort.

**Insertion sort** is a simple sorting algorithm, a comparison sort in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort

While implementing the insertion sort, we would try to main the following rules:

using System;

using System.Collections.Generic;

using System.Text;

namespace Sorting

{

class InsertionSort

{

static void Main(string[] args)

{

List<Int32> nums = new List<int>();

nums.Add(30);

nums.Add(10);

nums.Add(20);

nums.Add(40);

nums.Add(5);

nums.Add(8);

nums.Add(3);

InsertionSort sort = new InsertionSort();

sort.DoInsertionSort(ref nums);

foreach(int i in nums)

{

Console.WriteLine(i);

}

}

/// <summary>

///

/// </summary>

/// <param name=”numbersToBeSorted”>

/// The array of integers which needs to be sorted.

/// </param>

public void DoInsertionSort(ref List<Int32> numbersToBeSorted)

{

for (int j = 1; j < numbersToBeSorted.Count; j++)

{

//The key is the one which we would compare with each of

//the element and insert it appropriately.

int key = numbersToBeSorted[j];

//We just need to compare it with the previous element.

int i = j – 1;

//THE AWESOME TRICK:

// Since our state is we would always have the previous

//elements in sorted order, we would just traverse back

//and insert the key where the its most appropriate.

while (i > -1 && numbersToBeSorted[i] > key)

{

numbersToBeSorted[i + 1] = numbersToBeSorted[i];

i = i – 1;

}

numbersToBeSorted[i + 1] = key;

}

}

/*

*

* Out put would be:

3

5

8

10

20

30

40

Press any key to continue . . .

*/

}

}