Skip to main content

Insertion Sort


The implementation of insertion sort is very well known, but to improve upon the standard description this method uses System.Collections.ObjectModel.IComparable, allowing it to sort a range of types, and the class and methods are marked as static.  Both modifications make the methods more reusable than in typical examples.

             IComparable[] start = new IComparable[] {44, 2,4,1,6,7,33,25,5,2};
            IComparable[] result = InsertionSort.Sort(start);

             IComparable[] startAlpha = new IComparable[] { "r", "A", "z", "c", "a", "h"};
            IComparable[] resultAlpha = InsertionSort.Sort(startAlpha);

 The two lower routines are useful for quick sort, in that they will handle portions of arrays

 Class

 static class InsertionSort
    {
        /// <summary>
        /// Given a list of items, sorts by
        /// 1. examining each item from first position
        /// 2. calls method to insert value at correct sorted position
        /// </summary>
        /// <param name="startingList"></param>
        /// <returns></returns>
        public static IComparable[] Sort(IComparable[] startingList)
        {
            int arrayLength = startingList.Length;
            for (int counter = 0; counter < arrayLength; counter++)
            {
                startingList = Insert(startingList, counter);
            }
            return startingList;
        }

         /// <summary>
        /// 1. moves each value that is larger than current item's value back one
        /// 2. finaly inserting value at the correct position
        /// </summary>
        /// <param name="list"></param>
        /// <param name="position"></param>
        /// <returns></returns>
        private static IComparable[] Insert(IComparable[] list, int position)
        {
            int counter = position - 1;
            IComparable value = list[position];
            while (counter >= 0 && (list[counter].CompareTo(value) > 0))
            {
                list[counter + 1] = list[counter];
                counter = counter - 1;
            }
            list[counter + 1] = value;
            return list;
        }

         /// <summary>

        /// Given a list of items, sorts by
        /// 1. examining each item from starting index to endIndex, not necessarily the end of arry
        ///    - starting/ending indexes alllow this to be used with quick sort and portions of arrays
        /// 2. calls method to insert value at correct sorted position
        /// </summary>
        /// <param name="startingList"></param>
        /// <param name="startIndex"></param>
        /// <param name="endIndex"></param>
        /// <returns></returns>
        public static int[] Sort(int[] startingList, int startIndex, int endIndex)
        {
            for (int counter = startIndex; counter <= endIndex; counter++)
            {
                startingList = Insert(startingList, counter);
            }
            return startingList;
        }

         /// <summary>
        /// 1. moves each value that is larger than current item's value back one
        /// 2. finaly inserting value at correct position for value
        /// </summary>
        /// <param name="list"></param>
        /// <param name="position"></param>
        /// <returns></returns>
        private static int[] Insert(int[] list, int position)
        {
            int counter = position-1;
            int value = list[position];
            while (counter >= 0 && (list[counter].CompareTo(value) > 0))
            {
                list[counter + 1] = list[counter];
                counter = counter - 1;
            }
            list[counter + 1] = value;
            return list;
        }
    }
Labels:

Comments

Post a Comment

Popular posts from this blog

Heap Sort

Heap Sort is interesting because the use of the 'heapify' method that creates a binary tree as a flat array. First, a binary tree, also known as a heap , is created, and then the same function is used to sort the elements. In a heap, the first node in the array at zero (0) is the top node of the binary tree. The next two (2) items are the two (2) subnodes of the top node, and so on.  For each node at a position (positionIndex), its 2 subnodes are in the following positions: int left = 2 * positionIndex + 1; int right = 2 *  positionIndex + 2; The CommonMethods.Swap() function is a reusable class , since swapping values by position is a common action during these example sorts. Class using System; namespace Algorithms {     class HeapSort     {         public int[]  Sort()         {             //creates array             int[] arrayTo...
6 comments
Read more

Hash-based Search

An example of a hash-based search, although using dictionaries.  The code is designed to manage lists of Person objects, with unique Id's as the key value, with a rudimentary hash function to assign to various lists. Salient Characteristic(s) Useful for managing large unsorted lists Divides the items into smaller hash-based buckets (divide and conquer) Generally excellent performance Sensitive to the choice of hash function and data structures chosen Note The Id key is not rigorous enough to guarantee uniqueness, and a better key might need to be selected, e.g., SSN, to prevent the same person being entered twice. Code using System; using System.Collections.Generic; namespace Algorithms {     //Example object to add and find in Hash Search example     public class Person     {         private int _Id;         public int Id          {     ...
Post a Comment
Read more

Binary Search

This is the basic divide-and-conquer algorithm, requiring a sorted array. This repeatedly halves the remaining positions to search, until the value is found, or it determines that the value cannot be found. As mentioned, it requires a presorted array, or if unsorted, requires it is sorted. The benefits accrue in instances where the array is sorted once, but searched many times. On a hypothetical array of 100 items, a linear search has an average performances of O(n/2), or a search of half the positions, 50, to find the item. By comparison, the average performance of Binary Search is O(log n), which for 100 items translates into 4.6, a radically reduced number of iterations, but with greater requirements for logic and memory. Done in both C#, as an iterative while loop, and F#, as a recursion. C# using System; namespace Algorithms { class BinarySearch { public BinarySearch() { } public int Search(int num, int[] arrayToSearch) ...
Post a Comment
Read more