Skip to main content

Posts

Showing posts from June, 2012

Selection Sort

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])
                    {
                        //set new min
        …

QuickSort

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[] arrayToSort, int startIndex, int endI…

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 …

Algorithms in a Nutshell

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 Search ·Section 6.4. Single-Source Shortest Path ·Section 6.5. All Pa