Algorithms In .NET

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          {             get { return _Id; }             set { _Id = value; }          }                  private string _LastName;

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)

Because Linear Search is so simple, I thought of doing something a bit different, so this post includes code in F# as well as C#. F# //linear search, but with error handling for 'value not found' let LinearSearch num arr =      try         arr |> List.findIndex (fun x -> x = num)     with         | :? System.Collections.Generic.KeyNotFoundException -> -1 //create array to use let baseList = [3; 1; 7; 2; 9; 4; 1; 12; 25; 10; 11; 19; 22] //two examples, one that works, and one that returns an error of -1 let resultFound = LinearSearch 12 baseList let resultMissing = LinearSearch 23 baseList C# Code using System; namespace Algorithms {     class LinearSearch     {         public LinearSearch()         {         }                  public int Search(int num, int[] arrayToSearch)         {             //creates array             //int[] arrayToSort = { 11, 7, 22, 2, 33, 3, 17, 44, 4, 55, 5, 66, 6, 1, 77 };             int posFound = -1;

The following uses the divide-and-conquer method of resolution, by dividing the problem into smaller arrays, sorting each smaller array, then reinserting the subarrays back into the original array.  This is not a pure solution, in that it uses the .NET List, rather than a linked list struct. using System; using System.Collections; using System.Collections.Generic; namespace Algorithms {     class BucketSort     {         public int[] Sort()         {                //creates arbitrary array             int[] arrayToSort = { 11, 7, 22, 2, 33, 3, 17, 44, 4, 55, 5, 66, 6, 1, 77 };             //create bucket using hash, x/10             List<int>[] bucketList = CreateHashedArray(arrayToSort, 10);             //sort the bucket list back into the original array             ReorderList(bucketList, arrayToSort);             return arrayToSort;         }         private int hashFunction(int num, int buckets)         {             return num / buckets;         }

I did not spend a significant amount of time removing potential issues with this code, but then, neither do most examples of the Counting Sort; there are more interesting algorithms ahead.  The most obvious flaws in this particular implementation are as follows: It cannot handle negative integers It is designed only for integers.  using System; namespace Algorithms {     class CountingSort     {         public int[] Sort()         {             //creates array             int[] arrayToSort = { 2, 1, 2, 1, 3, 0, 3, 4, 4, 3, 0, 2, 1, 3, 5, 1, 3 };             //create array for bucket             int min = 0;              int max = 0;             for (int counter = 0; counter < arrayToSort.Length; counter++)             {                 if (arrayToSort[counter] < min)                 {                     min = arrayToSort[counter];                 }                 if (arrayToSort[counter] > max)                 {                     max = arrayToSo

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[] arrayToSort = { 11, 1, 22, 2, 33, 3, 44, 4, 55, 5, 66, 6, 7, 77, 88 };                         //creates a heap             BuildH

During sorts, swapping elements is a common function, and this static class can be used instead of writing redundant code.  In this case, for the example code on this site, the function only swaps integer values in an integer-based array, but the idea could easily be overloaded for numerous array-like structures.  Usage The order of the numbers to swap is immaterial.  Simply pass it the zero-based positions of the items the code needs to swap. CommonMethods.Swap(arrayToSort, firstNumber, second number); Class using System; namespace Algorithms {     static class CommonMethods     {         public static int[] Swap(int[] arrayToUse, int itemOneIndex, int itemTwoIndex)         {             int tempValueHolder = arrayToUse[itemOneIndex];             arrayToUse[itemOneIndex] = arrayToUse[itemTwoIndex];             arrayToUse[itemTwoIndex] = tempValueHolder;             return arrayToUse;         }     } }

The least intelligent sorting algorithm, it typically has the worst performance of sorting routines, and learns nothing to improve its actions as it traverse the array: Class using System; namespace Algorithms {     class SelectionSort     {         public SelectionSort()         {             int[] arrayToSort = { 11, 1, 22, 2, 33, 3, 44, 4, 55, 5, 66, 6, 7, 77 };             Sort(arrayToSort);             Console.WriteLine("End");         }         public int[] Sort(int[] arrayToSort)         {             int currentMin;             int max = arrayToSort.Length - 1;             for (int counter = 0; counter < max - 1; counter++)             {                 currentMin = arrayToSort[counter];                 int newMinCounter = counter;                 for (int innerCounter = counter + 1; innerCounter < max; innerCounter++)                 {                      if (arrayToSort[innerCounter] < arrayToSort[newMinCounter])                

This is similar to Median Sort, which I skipped, but Quicksort supersedes it.  This uses a similar strategy, but instead of finding the median, it accepts any value for the pivot index, then simply performs an insertion sort on the resulting partitioned array of 2 sub-arrays.  The insertion sort used here is from a prior post on Insertion Sort . Class using System; namespace Algorithms {     class QuickSort     {         public void Sort()         {             //creates array             int[] arrayToSort = { 11, 1, 22, 2, 33, 3, 44, 4, 55, 5, 66, 6, 7, 77 };             //gets pivotIndex, set at midpoint of arry             int pivotIndex = Partition(arrayToSort, 0, arrayToSort.Length - 1, (arrayToSort.Length - 1)/2);             //sorts each ~half array             arrayToSort = InsertionSort.Sort(arrayToSort, 0, pivotIndex);             arrayToSort = InsertionSort.Sort(arrayToSort, pivotIndex, arrayToSort.Length - 1);        }         public int Partition(int[

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 in

The following are some of the the chapters from Algorithm's in a Nutshell, from which I will produce code in .NET, specifically C#, VB.NET or F#, to clarify the principles for myself. Chapter 4. Sorting Algorithms ·        Section 4.1. Overview ·        Section 4.2. Insertion Sort ·        Section 4.3. Median Sort ·        Section 4.4. Quicksort ·        Section 4.5. Selection Sort ·        Section 4.6. Heap Sort ·        Section 4.7. Counting Sort ·        Section 4.8. Bucket Sort ·        Section 4.9. Criteria for Choosing a Sorting Algorithm ·        Section 4.10. References Chapter 5. Searching ·        Section 5.1. Overview ·        Section 5.2. Sequential Search ·        Section 5.3. Binary Search ·        Section 5.4.  Hash-based Search ·        Section 5.5. Binary Tree Search Chapter 6. Graph Algorithms ·        Section 6.1. Overview ·        Section 6.2. Depth-First Search ·        Section 6.3. Breadth-First S