jump to navigation

Insertion Sort June 10, 2008

Posted by Thinker in Algorithms.
Tags: , ,
trackback

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:

1. While we begin sorting we would sort from the second array position.
2. We keep traversing the array and take the next element in the array and position it such that it is in the sorted order.
 
The implementation of the insertion sort in C# language is as follows:

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

    }
}

 

Advertisements

Comments»

No comments yet — be the first.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: