Thoughts

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 . . .
         */

    }
}