Searching and Sorting Algorithms via C#

logicchild

4.67/5 (12 votes)

5 Apr 2011CPOL4 min read

151.1K

2.2K

An article that details coding algorithms with C#.

Download source code - 17.3 KB

Introduction and References

This article will focus on the sorting and searching algorithms enabled via the .NET Framework's Class Library. As such, it assumes that the reader has a working knowledge of Generics. The FCL provides several classes, called collections, which are used to store groups of related objects. Along with methods for organizing, storing, and retrieving data, these classes provides methods for sorting and searching. Consider the generic List<T> class found in the System.Collections.Generic namespace and the ArrayList class found in the System.Collections namespace. Both of these classes have properties that are very similar to C# arrays and, in addition, also come with their own methods for performing efficient sorting and searching. However, one key advantage of using collection classes over conventional arrays is that collections can dynamically grow and shrink as their number of elements change. Arrays, on the other hand, do not automatically adjust their size at runtime to accommodate changes in their initial number of allotted elements unless the one writing the code manually codes in a new array or uses the array class' Resize method. Note that the referenced material contained within this article was obtained from the book "Numerical Methods, Algorithms, and Tools in C#", written by Waldemar Dos Passos, CRC Press.

A sorting algorithm is essentially a sort of cookbook containing code instructions for organizing the elements of a list into a well-defined numerical or alphabetical order. A list is an abstract concept consisting of a finite collection of fixed-length entities that can be arranged either in random order or in an increasing or decreasing sequential order. In actual practice, technical documentation asserts that a list is usually expressed in the form of an array or a more advanced data structure such as a linked list. If we are sorting data, we are obviously inputting unsorted data into the computational model. The output is sorted data. Let's look at a basic example of a C# algorithm called Bubble Sort:

using  System;
using  System.Collections.Generic;
using  System.Linq;
using  System.Text;
using System.Collections;
public class Program
{
    public static void bubbleSort1(ref int[] x)
    {
        bool exchanges;
        do
        {
            exchanges = false;
            for (int i = 0; i < x.Length - 1; i++)
            {
                if (x[i] > x[i + 1])
                {
                    // Exchange elements
                    int temp = x[i];
                    x[i] = x[i + 1];
                    x[i + 1] = temp;
                    exchanges = true;
                }
            }
        } while (exchanges);
    }

    public static void DisplayElements(ref int[] xArray, char status, string sortname)
    {
        if (status == 'a')
            Console.WriteLine("After sorting using algorithm: " + sortname);
        else
            Console.WriteLine("Before sorting");
        for (int i = 0; i <= xArray.Length - 1; i++)
        {
            if ((i != 0) && (i % 10 == 0))
                Console.Write("\n");
            Console.Write(xArray[i] + " ");
        }
        Console.ReadLine();
     }


    static void MixDataUp(ref int[] x, Random rdn)
    {
        for (int i = 0; i <= x.Length - 1; i++)
        {
            x[i] = (int)(rdn.NextDouble() * x.Length);
        }
    }

    public static void Main(string[] args)
    {
        Console.WriteLine("Sorting Algorithms Demo Code\n\n");

        const int nItems = 20;
        Random rdn = new Random(nItems);
        int[] xdata = new int[nItems];
        MixDataUp(ref xdata, rdn);
        DisplayElements(ref xdata, 'b', "");
        Console.WriteLine();
        bubbleSort1(ref xdata);
        DisplayElements(ref xdata, 'a', "bubbleSort1");
        Console.WriteLine("\n\n");
        Console.WriteLine("Press Enter to Exit...");
     }
}

Admittedly, the amount of data in this example is very small. The example code, however, is meant to demonstrate how it works. Take a look at the output:

Sorting Algorithms Demo Code
Before sorting
3 13 14 16 4 0 17 9 9 12
0 1 7 17 19 10 5 7 4 1

After sorting using algorithm: bubbleSort1
0 0 1 1 3 4 4 5 7 7
9 9 10 12 13 14 16 17 17 19
Press Enter to Exit...

Bubble Sort works by stepping through the entire list to be sorted while comparing two items at a time and swapping their positions if they are found to be in the wrong order. This process is repeated until no swaps are needed, thereby indicating that the list has been sorted. The algorithm gets its name from the way smaller elements seem to bubble to the top of the list. In fact, one of the many performance problems with the Bubble Sort algorithm is that it is inefficient with large amounts of data. MIT Open Course Ware offers a course on algorithms and insists that a major part of algorithm design is performance analysis. Here is another example of the Bubble Sort algorithm:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

public class Program
{
    public static void bubbleSort2(ref int[] x)
    {
        for (int pass = 1; pass < x.Length - 1; pass++)
        {
            // Count how many times this next loop
            // becomes shorter and shorter
            for (int i = 0; i < x.Length - pass; i++)
            {
                if (x[i] > x[i + 1])
                {
                    // Exchange elements
                    int temp = x[i];
                    x[i] = x[i + 1];
                    x[i + 1] = temp;
                }
            }
        }
    }

    public static void DisplayElements(ref int[] xArray, char status, string sortname)
    {
        if (status == 'a')
            Console.WriteLine("After sorting using algorithm: " + sortname);
        else
            Console.WriteLine("Before sorting");
        for (int i = 0; i <= xArray.Length - 1; i++)
        {
            if ((i != 0) && (i % 10 == 0))
                Console.Write("\n");
            Console.Write(xArray[i] + " ");
        }
        Console.ReadLine();
     }

    static void MixDataUp(ref int[] x, Random rdn)
    {
        for (int i = 0; i <= x.Length - 1; i++)
        {
            x[i] = (int)(rdn.NextDouble() * x.Length);
        }
    }

    public static void Main(string[] args)
    {
        Console.WriteLine("Sorting Algorithms Demo Code\n\n");
        const int nItems = 20;
        Random rdn = new Random(nItems);
        int[] xdata = new int[nItems];

        MixDataUp(ref xdata, rdn);
        DisplayElements(ref xdata, 'b', "");
        Console.WriteLine();
        bubbleSort2(ref xdata);
        DisplayElements(ref xdata, 'a', "bubbleSort2");
        Console.WriteLine("\n\n");
        Console.WriteLine("Press Enter to Exit...");
     }
}

Notice the output. It is relatively the same, but coded differently to make it more efficient with the 20 data elements:

Sorting Algorithms Demo Code
Before sorting
3 13 14 16 4 0 17 9 9 12
0 1 7 17 19 10 5 7 4 1

After sorting using algorithm: bubbleSort2
0 0 1 1 3 4 4 5 7 7
9 9 10 12 13 14 16 17 17 19
Press Enter to Exit...

The Cocktail Sort, also known as the Bi-directional Bubble Sort, is just another slightly improved variation of the fundamental Bubble Sort algorithm. The difference between the Cocktail and the Bubble Sort algorithms is that instead of repeatedly iterating through an input list from bottom to top, the Cocktail Sort iterates alternating from bottom to top and then from top to bottom. By performing bidirectional iterations, the Cocktail Sort can achieve a slightly better performance time than the standard Bubble Sort algorithm which only iterates through the input list in one direction and therefore can only reposition items by one step per iteration. Here is an example of the Cocktail Sort algorithm:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

public class Program
{
    public static void CocktailSort(ref int[] x)
    {
        for (int k = x.Length - 1; k > 0; k--)
        {
            bool swapped = false;
            for (int i = k; i > 0; i--)
                if (x[i] < x[i - 1])
                {
                    // swap
                    int temp = x[i];
                    x[i] = x[i - 1];
                    x[i - 1] = temp;
                    swapped = true;
                }

            for (int i = 0; i < k; i++)
                if (x[i] > x[i + 1])
                {
                    // swap
                    int temp = x[i];
                    x[i] = x[i + 1];
                    x[i + 1] = temp;
                    swapped = true;
                }

            if (!swapped)
                break;
        }
    }

    public static void DisplayElements(ref int[] xArray, char status, string sortname)
    {
        if (status == 'a')
            Console.WriteLine("After sorting using algorithm: " + sortname);
        else
            Console.WriteLine("Before sorting");
        for (int i = 0; i <= xArray.Length - 1; i++)
        {
            if ((i != 0) && (i % 10 == 0))
                Console.Write("\n");
            Console.Write(xArray[i] + " ");
        }
        Console.ReadLine();
    }

    static void MixDataUp(ref int[] x, Random rdn)
    {
        for (int i = 0; i <= x.Length - 1; i++)
        {
            x[i] = (int)(rdn.NextDouble() * x.Length);
        }
    }

    public static void Main(string[]  args) {
    
    const int nItems = 50;
    Random rdn = new Random(nItems);
    int[] xdata = new int[nItems];
    MixDataUp(ref xdata, rdn);
    Console.WriteLine();
    DisplayElements(ref xdata, 'b', "");
    Console.WriteLine();
    CocktailSort(ref xdata);
    DisplayElements(ref xdata, 'a', "CocktailSort");
    Console.WriteLine("\n\n");
    }
}

Here is the output of the different approach. Notice that again we use a method that mixes up the data, displays the data, calls the sorting algorithm, and displays the results:

Before sorting

Before sorting
42 24 35 11 39 12 15 26 8 35
6 25 0 24 49 12 44 49 1 33
23 5 22 24 30 34 46 33 17 17
32 31 20 12 5 46 22 22 45 17
44 30 36 46 13 41 17 12 1 41

After sorting using algorithm: CocktailSort
0 1 1 5 5 6 8 11 12 12
12 12 13 15 17 17 17 17 20 22
22 22 23 24 24 24 25 26 30 30
31 32 33 33 34 35 35 36 39 41
41 42 44 44 45 46 46 46 49 49

The downloadable zip file contains the above sorting examples, along with a plethora of other sorting algorithms and searching algorithms. Describing them all would be out of the scope of this article. At this point, we should consider searching algorithms.

Searching Algorithms

Linear Search is a search algorithm also known as Sequential Search, that is apt for searching a list of data for a particular value. It operates by checking every element of a list one at a time in sequence until a match is found.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

public class Program
{
    public static int LinearSearch(ref int[] x, int valueToFind)
    {
        for (int i = 0; i < x.Length; i++)
        {
            if (valueToFind == x[i])
            {
                return i;
            }
        }
        return -1;
    }

    public static void DisplayElements(ref int[] xArray, char status, string sortname)
    {
        if (status == 'a')
            Console.WriteLine("After sorting using algorithm: " + sortname);
        else
            Console.WriteLine("Before sorting");
        for (int i = 0; i <= xArray.Length - 1; i++)
        {
            if ((i != 0) && (i % 10 == 0))
                Console.Write("\n");
            Console.Write(xArray[i] + " ");
        }
        Console.ReadLine();
    }

    static void MixDataUp(ref int[] x, Random rdn)
    {
        for (int i = 0; i <= x.Length - 1; i++)
        {
            x[i] = (int)(rdn.NextDouble() * x.Length);
        }
    }

    public static void Main(string[]  args) {
        const int nItems = 20;
        Random rdn = new Random(nItems);
        int[] xdata = new int[nItems];
        MixDataUp(ref xdata, rdn); //Randomize data to be searched
        DisplayElements(ref xdata, 'b', ""); //Display random data

        Console.WriteLine("Using LINEAR SEARCH ALGORITHM " + 
                "to look for 4th data entry in randomized list");
        //Look for the 4th data entry in the list
        int location = LinearSearch(ref xdata, xdata[4]);
        if (location == -1)
            Console.WriteLine("Value was not found in list");
        else
            Console.WriteLine("Found it at location = {0}", location);
        location = LinearSearch(ref xdata, 19); //Look for the number 19 in the list.
        if (location == -1)
            Console.WriteLine("Value of 19 was not found in list");
        else
            Console.WriteLine("Value of 19 was found at location = {0}", location);
        Console.WriteLine("\n\n");
    }
}

Here is the output:

Before sorting
3 13 14 16 4 0 17 9 9 12
0 1 7 17 19 10 5 7 4 1
Using LINEAR SEARCH ALGORITHM to look for 4th data entry in randomized list
Found it at location = 4
Value of 19 was found at  location = 14

Recall that an array, as signified by brackets [], is normally zero-based. That is, if there are [4] elements, then they are 0, 1, 2, and 3. Check this by verifying the location in the output of the code shown above. Now, let's take a look at code that consolidates the entire solution file:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

public class Program
{
    #region Bubble Sorts

    public static void bubbleSort1(ref int[] x)
    {
        bool exchanges;
        do
        {
            exchanges = false;
            for (int i = 0; i < x.Length - 1; i++)
            {
                if (x[i] > x[i + 1])
                {
                    // Exchange elements
                    int temp = x[i];
                    x[i] = x[i + 1];
                    x[i + 1] = temp;
                    exchanges = true;
                }
            }
        } while (exchanges);
    }

    public static void bubbleSort2(ref int[] x)
    {
        for (int pass = 1; pass < x.Length - 1; pass++)
        {
            // Count how many times this next loop
            // becomes shorter and shorter
            for (int i = 0; i < x.Length - pass; i++)
            {
                if (x[i] > x[i + 1])
                {
                    // Exchange elements
                    int temp = x[i];
                    x[i] = x[i + 1];
                    x[i + 1] = temp;
                }
            }
        }
    }

    public static void bubbleSort3(ref int[] x)
    {
        bool exchanges;
        int n = x.Length;
        do
        {
            n--; // Make loop smaller each time.
            // and assume this is last pass over array
            exchanges = false;
            for (int i = 0; i < x.Length - 1; i++)
            {
                if (x[i] > x[i + 1])
                {
                    // Exchange elements
                    int temp = x[i];
                    x[i] = x[i + 1];
                    x[i + 1] = temp;
                    exchanges = true;
                }
            }
        } while (exchanges);
    }

    public static void bubbleSortRange(ref int[] x)
    {
        int lowerBound = 0; // First position to compare.
        int upperBound = x.Length - 1; // First position NOT to compare.
        int n = x.Length - 1;

        // Continue making passes while there is a potential exchange.
        while (lowerBound <= upperBound)
        {
            int firstExchange = n;  // assume impossibly high index for low end.
            int lastExchange = -1; // assume impossibly low index for high end.

            // Make a pass over the appropriate range.
            for (int i = lowerBound; i < upperBound; i++)
            {
                if (x[i] > x[i + 1])
                {
                    // Exchange elements
                    int temp = x[i];
                    x[i] = x[i + 1];
                    x[i + 1] = temp;
                    // Remember first and last exchange indexes.
                    if (i < firstExchange)
                    {   // True only for first exchange.
                        firstExchange = i;
                    }
                    lastExchange = i;
                }
            }

            //--- Prepare limits for next pass.
            lowerBound = firstExchange - 1;
            if (lowerBound < 0)
            {
                lowerBound = 0;
            }
            upperBound = lastExchange;
        }
    }
    #endregion

    #region Cocktail Sort
    public static void CocktailSort(ref int[] x)
    {
        for (int k = x.Length - 1; k > 0; k--)
        {
            bool swapped = false;
            for (int i = k; i > 0; i--)
                if (x[i] < x[i - 1])
                {
                    // swap
                    int temp = x[i];
                    x[i] = x[i - 1];
                    x[i - 1] = temp;
                    swapped = true;
                }

            for (int i = 0; i < k; i++)
                if (x[i] > x[i + 1])
                {
                    // swap
                    int temp = x[i];
                    x[i] = x[i + 1];
                    x[i + 1] = temp;
                    swapped = true;
                }

            if (!swapped)
                break;
        }
    }
    #endregion

    #region Odd Even Sort
    public static void OddEvenSort(ref int[] x)
    {
        int temp;
        for (int i = 0; i < x.Length / 2; ++i)
        {
            for (int j = 0; j < x.Length - 1; j += 2)
            {
                if (x[j] > x[j + 1])
                {
                    temp = x[j];
                    x[j] = x[j + 1];
                    x[j + 1] = temp;
                }
            }

            for (int j = 1; j < x.Length - 1; j += 2)
            {
                if (x[j] > x[j + 1])
                {
                    temp = x[j];
                    x[j] = x[j + 1];
                    x[j + 1] = temp;
                }
            }
        }
    }
    #endregion

    #region Comb Sort
    public static int newGap(int gap)
    {
        gap = gap * 10 / 13;
        if (gap == 9 || gap == 10)
            gap = 11;
        if (gap < 1)
            return 1;
        return gap;
    }

    public static void CombSort(ref int[] x)
    {
        int gap = x.Length;
        bool swapped;
        do
        {
            swapped = false;
            gap = newGap(gap);
            for (int i = 0; i < (x.Length - gap); i++)
            {
                if (x[i] > x[i + gap])
                {
                    swapped = true;
                    int temp = x[i];
                    x[i] = x[i + gap];
                    x[i + gap] = temp;
                }
            }
        } while (gap > 1 || swapped);
    }
    #endregion

    #region Gnome Sort
    public static void GnomeSort(ref int[] x)
    {
        int i = 0;
        while (i < x.Length)
        {
            if (i == 0 || x[i - 1] <= x[i]) i++;
            else
            {
                int temp = x[i];
                x[i] = x[i - 1];
                x[--i] = temp;
            }
        }
    }
    #endregion

    #region Insertion Sort
    public static void InsertionSort(ref int[] x)
    {
        int n = x.Length - 1;
        int i, j, temp;

        for (i = 1; i <= n; ++i)
        {
            temp = x[i];
            for (j = i - 1; j >= 0; --j)
            {
                if (temp < x[j]) x[j + 1] = x[j];
                else break;
            }
            x[j + 1] = temp;
        }
    }
    #endregion

    #region Quick Sort

    public static void QuickSort(ref int[] x)
    {
        qs(x, 0, x.Length - 1);
    }

    public static void qs(int[] x, int left, int right)
    {
        int i, j;
        int pivot, temp;

        i = left;
        j = right;
        pivot = x[(left + right) / 2];

        do
        {
            while ((x[i] < pivot) && (i < right)) i++;
            while ((pivot < x[j]) && (j > left)) j--;

            if (i <= j)
            {
                temp = x[i];
                x[i] = x[j];
                x[j] = temp;
                i++; j--;
            }
        } while (i <= j);

        if (left < j) qs(x, left, j);
        if (i < right) qs(x, i, right);
    }

    #endregion

    #region Shell Sort
    
    public static void ShellSort(ref int[] x)
    {
        int i, j, temp;
        int increment = 3;

        while (increment > 0)
        {
            for (i = 0; i < x.Length; i++)
            {
                j = i;
                temp = x[i];

                while ((j >= increment) && (x[j - increment] > temp))
                {
                    x[j] = x[j - increment];
                    j = j - increment;
                }

                x[j] = temp;
            }

            if (increment / 2 != 0)
            {
                increment = increment / 2;
            }
            else if (increment == 1)
            {
                increment = 0;
            }
            else
            {
                increment = 1;
            }
        }
    }
    #endregion

    #region Selection Sort
    
    public static void SelectionSort(ref int[] x)
    {
        int i, j;
        int min, temp;

        for (i = 0; i < x.Length - 1; i++)
        {
            min = i;
            for (j = i + 1; j < x.Length; j++)
            {
                if (x[j] < x[min])
                {
                    min = j;
                }
            }
            temp = x[i];
            x[i] = x[min];
            x[min] = temp;
        }
    }
    #endregion

    #region Merge Sort
    
    public static void MergeSort(ref int[] x, int left, int right)
    {
        if (left < right)
        {
            int middle = (left + right) / 2;
            MergeSort(ref x, left, middle);
            MergeSort(ref x, middle + 1, right);
            Merge(ref x, left, middle, middle + 1, right);
        }
    }

    public static void Merge(ref int[] x, int left, int middle, int middle1, int right)
    {
        int oldPosition = left;
        int size = right - left + 1;
        int[] temp = new int[size];
        int i = 0;

        while (left <= middle && middle1 <= right)
        {
            if (x[left] <= x[middle1])
                temp[i++] = x[left++];
            else
                temp[i++] = x[middle1++];
        }
        if (left > middle)
            for (int j = middle1; j <= right; j++)
                temp[i++] = x[middle1++];
        else
            for (int j = left; j <= middle; j++)
                temp[i++] = x[left++];
        Array.Copy(temp, 0, x, oldPosition, size);
    }
    #endregion

    #region Bucket Sort

    public static void BucketSort(ref int[] x)
    {
        //Verify input
        if (x == null || x.Length <= 1)
            return;

        //Find the maximum and minimum values in the array
        int maxValue = x[0];
        int minValue = x[0];

        for (int i = 1; i < x.Length; i++)
        {
            if (x[i] > maxValue)
                maxValue = x[i];

            if (x[i] < minValue)
                minValue = x[i];
        }

        //Create a temporary "bucket" to store the values in order
        //each value will be stored in its corresponding index
        //scooting everything over to the left as much as possible (minValue)
        LinkedList<int>[] bucket = new LinkedList<int>[maxValue - minValue + 1];

        //Move items to bucket
        for (int i = 0; i < x.Length; i++)
        {
            if (bucket[x[i] - minValue] == null)
                bucket[x[i] - minValue] = new LinkedList<int>();

            bucket[x[i] - minValue].AddLast(x[i]);
        }

        //Move items in the bucket back to the original array in order
        int k = 0; //index for original array
        for (int i = 0; i < bucket.Length; i++)
        {
            if (bucket[i] != null)
            {
                LinkedListNode<int> node = bucket[i].First; //start add head of linked list

                while (node != null)
                {
                    x[k] = node.Value; //get value of current linked node
                    node = node.Next; //move to next linked node
                    k++;
                }
            }
        }
    }
    #endregion

    #region Heap Sort
    
    public static void Heapsort(ref int[] x)
    {
        int i;
        int temp;
        int n = x.Length;

        for (i = (n / 2) - 1; i >= 0; i--)
        {
            siftDown(ref x, i, n);
        }

        for (i = n - 1; i >= 1; i--)
        {
            temp = x[0];
            x[0] = x[i];
            x[i] = temp;
            siftDown(ref x, 0, i - 1);
        }
    }

    public static void siftDown(ref int[] x, int root, int bottom)
    {
        bool done = false;
        int maxChild;
        int temp;

        while ((root * 2 <= bottom) && (!done))
        {
            if (root * 2 == bottom)
                maxChild = root * 2;
            else if (x[root * 2] > x[root * 2 + 1])
                maxChild = root * 2;
            else
                maxChild = root * 2 + 1;

            if (x[root] < x[maxChild])
            {
                temp = x[root];
                x[root] = x[maxChild];
                x[maxChild] = temp;
                root = maxChild;
            }
            else
            {
                done = true;
            }
        }
    }
    #endregion

    #region Count Sort
        
    public static void Count_Sort(ref int[] x)
    {
        try
        {
            int i = 0;
            int k = FindMax(x); //Finds max value of input array

            // output array holds the sorted output
            int[] output = new int[x.Length];

            // provides temperarory storage 
            int[] temp = new int[k + 1];
            for (i = 0; i < k + 1; i++)
            {
                temp[i] = 0;
            }

            for (i = 0; i < x.Length; i++)
            {
                temp[x[i]] = temp[x[i]] + 1;
            }

            for (i = 1; i < k + 1; i++)
            {
                temp[i] = temp[i] + temp[i - 1];
            }

            for (i = x.Length - 1; i >= 0; i--)
            {
                output[temp[x[i]] - 1] = x[i];
                temp[x[i]] = temp[x[i]] - 1;
            }

            for (i = 0; i < x.Length; i++)
            {
                x[i] = output[i];
            }
        }

        catch (System.Exception e)
        {
            Console.WriteLine(e.ToString());
            Console.ReadLine();
        }
    }
    #endregion

    #region Radix Sort
    
    //RadixSort takes an array and the number of bits used as 
    //the key in each iteration.
    public static void RadixSort(ref int[] x, int bits)
    {
        //Use an array of the same size as the original array 
        //to store the result of each iteration.
        int[] b = new int[x.Length];
        int[] b_orig = b;

        //Mask is the bitmask used to extract the sort key. 
        //We start with the bits least significant bits and
        //left-shift it the same amount at each iteration. 
        //When all the bits are shifted out of the word, we are done.
        int rshift = 0;
        for (int mask = ~(-1 << bits); mask != 0; mask <<= bits, rshift += bits)
        {
            //An array is needed to store the count for each key value.
            int[] cntarray = new int[1 << bits];

            //Count each key value
            for (int p = 0; p < x.Length; ++p)
            {
                int key = (x[p] & mask) >> rshift;
                ++cntarray[key];
            }

            //Sum up how many elements there are with lower 
            //key values, for each key.
            for (int i = 1; i < cntarray.Length; ++i)
                cntarray[i] += cntarray[i - 1];

            //The values in cntarray are used as indexes 
            //for storing the values in b. b will then be
            //completely sorted on this iteration's key. 
            //Elements with the same key value are stored 
            //in their original internal order.
            for (int p = x.Length - 1; p >= 0; --p)
            {
                int key = (x[p] & mask) >> rshift;
                --cntarray[key];
                b[cntarray[key]] = x[p];
            }

            //Swap the a and b references, so that the 
            //next iteration works on the current b, 
            //which is now partially sorted.
            int[] temp = b; b = x; x = temp;
        }
    }

    #endregion

    #region Linear Search
    public static int LinearSearch(ref int[] x, int valueToFind)
    {
        for (int i = 0; i < x.Length; i++)
        {
            if (valueToFind == x[i])
            {
                return i;
            }
        }
        return -1;
    }
    #endregion

    #region Binary Search

    public static int BinSearch(ref int[] x, int searchValue)
    {
        // Returns index of searchValue in sorted array x, or -1 if not found
        int left = 0;
        int right = x.Length;
        return binarySearch(ref x, searchValue, left, right);
    }

    public static int binarySearch(ref int[] x, int searchValue, int left, int right)
    {
        if (right < left)
        {
            return -1;
        }
        int mid = (left + right) >> 1;
        if (searchValue > x[mid])
        {
            return binarySearch(ref x, searchValue, mid + 1, right);
        }
        else if (searchValue < x[mid])
        {
            return binarySearch(ref x, searchValue, left, mid - 1);
        }
        else
        {
            return mid;
        }
    }
    #endregion

    #region Interpolation Search

    public static int InterpolationSearch(ref int[] x, int searchValue)
    {
        // Returns index of searchValue in sorted input data
        // array x, or -1 if searchValue is not found
        int low = 0;
        int high = x.Length - 1;
        int mid;

        while (x[low] < searchValue && x[high] >= searchValue)
        {
            mid = low + ((searchValue - x[low]) * (high - low)) / (x[high] - x[low]);

            if (x[mid] < searchValue)
                low = mid + 1;
            else if (x[mid] > searchValue)
                high = mid - 1;
            else
                return mid;
        }

        if (x[low] == searchValue)
            return low;
        else
            return -1; // Not found
    }
    #endregion

    #region Nth Largest

    public static int NthLargest1(int[] array, int n)
    {
        //Copy input data array into a temporary array
        //so that original array is unchanged
        int[] tempArray = new int[array.Length];
        array.CopyTo(tempArray, 0);
        //Sort the array
        QuickSort(ref tempArray);
        //Return the n-th largest value in the sorted array
        return tempArray[tempArray.Length - n];
    }

    public static int NthLargest2(int[] array, int k)
    {
        int maxIndex;
        int maxValue;

        //Copy input data array into a temporary array
        //so that original array is unchanged
        int[] tempArray = new int[array.Length];
        array.CopyTo(tempArray, 0);

        for (int i = 0; i < k; i++)
        {
            maxIndex = i;       // index of minimum element
            maxValue = tempArray[i];// assume minimum is the first array element
            for (int j = i + 1; j < tempArray.Length; j++)
            {
                // if we've located a higher value
                if (tempArray[j] > maxValue)
                {   // capture it
                    maxIndex = j;
                    maxValue = tempArray[j];
                }
            }
            Swap(ref tempArray[i], ref tempArray[maxIndex]);
        }
        return tempArray[k - 1];
    }
    #endregion

    #region Mth Smallest

    public static int MthSmallest1(int[] array, int m)
    {
        //Copy input data array into a temporary array
        //so that original array is unchanged
        int[] tempArray = new int[array.Length];
        array.CopyTo(tempArray, 0);
        //Sort the array
        QuickSort(ref tempArray);
        //Return the m-th smallest value in the sorted array
        return tempArray[m - 1];
    }

    public static int MthSmallest2(int[] array, int m)
    {
        int minIndex;
        int minValue;

        //Copy input data array into a temporary array
        //so that original array is unchanged
        int[] tempArray = new int[array.Length];
        array.CopyTo(tempArray, 0);

        for (int i = 0; i < m; i++)
        {
            minIndex = i;      // index of minimum element
            minValue = tempArray[i];// assume minimum is the first array element
            for (int j = i + 1; j < array.Length; j++)
            {
                if (tempArray[j] < minValue)
                {   // capture it
                    minIndex = j;
                    minValue = tempArray[j];
                }
            }
            Swap(ref tempArray[i], ref tempArray[minIndex]);
        }
        return tempArray[m - 1];
    }
    #endregion
    
    #region Miscellaneous Utilities
    
    public static int FindMax(int[] x)
    {
        int max = x[0];
        for (int i = 1; i < x.Length; i++)
        {
            if (x[i] > max) max = x[i];
        }
        return max;
    }

    public static int FindMin(int[] x)
    {
        int min = x[0];
        for (int i = 1; i < x.Length; i++)
        {
            if (x[i] < min) min = x[i];
        }
        return min;
    }

    static void MixDataUp(ref int[] x, Random rdn)
    {
        for (int i = 0; i <= x.Length - 1; i++)
        {
            x[i] = (int)(rdn.NextDouble() * x.Length);
        }
    }

    static void Swap(ref int left, ref int right)
    {
        int temp = left;
        left = right;
        right = temp;
    }

    // Determines if int array is sorted from 0 -> Max
    public static bool IsSorted(int[] arr)
    {
        for (int i = 1; i < arr.Length; i++)
        {
            if (arr[i - 1] > arr[i])
            {
                return false;
            }
        }
        return true;
    }

    // Determines if string array is sorted from A -> Z
    public static bool IsSorted(string[] arr)
    {
        for (int i = 1; i < arr.Length; i++)
        {
            if (arr[i - 1].CompareTo(arr[i]) > 0) // If previous is bigger, return false
            {
                return false;
            }
        }
        return true;
    }

    // Determines if int array is sorted from Max -> 0
    public static bool IsSortedDescending(int[] arr)
    {
        for (int i = arr.Length - 2; i >= 0; i--)
        {
            if (arr[i] < arr[i + 1])
            {
                return false;
            }
        }
        return true;
    }

    // Determines if string array is sorted from Z -> A
    public static bool IsSortedDescending(string[] arr)
    {
        for (int i = arr.Length - 2; i >= 0; i--)
        {
            if (arr[i].CompareTo(arr[i + 1]) < 0) // If previous is smaller, return false
            {
                return false;
            }
        }
        return true;
    }

    public static void DisplayElements(ref int[] xArray, char status, string sortname)
    {
        if (status == 'a')
            Console.WriteLine("After sorting using algorithm: " + sortname);
        else
            Console.WriteLine("Before sorting");
        for (int i = 0; i <= xArray.Length - 1; i++)
        {
            if ((i != 0) && (i % 10 == 0))
                Console.Write("\n");
            Console.Write(xArray[i] + " ");
        }
        Console.ReadLine();
    }
    #endregion

    static void Main(string[] args)
    {
        Console.WriteLine("Sorting Algorithms Demo Code\n\n");

        const int nItems = 20;
        Random rdn = new Random(nItems);
        int[] xdata = new int[nItems];

        MixDataUp(ref xdata, rdn);
        DisplayElements(ref xdata, 'b', "");
        bubbleSort1(ref xdata);
        DisplayElements(ref xdata, 'a', "bubbleSort1");
        Console.WriteLine("\n\n");

        MixDataUp(ref xdata, rdn);
        DisplayElements(ref xdata, 'b', "");
        bubbleSort2(ref xdata);
        DisplayElements(ref xdata, 'a', "bubbleSort2");
        Console.WriteLine("\n\n");

        MixDataUp(ref xdata, rdn);
        DisplayElements(ref xdata, 'b', "");
        bubbleSort3(ref xdata);
        DisplayElements(ref xdata, 'a', "bubbleSort3");
        Console.WriteLine("\n\n");

        MixDataUp(ref xdata, rdn);
        DisplayElements(ref xdata, 'b', "");
        bubbleSortRange(ref xdata);
        DisplayElements(ref xdata, 'a', "bubbleSortRange");
        Console.WriteLine("\n\n");

        MixDataUp(ref xdata, rdn);
        DisplayElements(ref xdata, 'b', "");
        CocktailSort(ref xdata);
        DisplayElements(ref xdata, 'a', "CocktailSort");
        Console.WriteLine("\n\n");

        MixDataUp(ref xdata, rdn);
        DisplayElements(ref xdata, 'b', "");
        OddEvenSort(ref xdata);
        DisplayElements(ref xdata, 'a', "OddEvenSort");
        Console.WriteLine("\n\n");

        MixDataUp(ref xdata, rdn);
        DisplayElements(ref xdata, 'b', "");
        CombSort(ref xdata);
        DisplayElements(ref xdata, 'a', "CombSort");
        Console.WriteLine("\n\n");

        MixDataUp(ref xdata, rdn);
        DisplayElements(ref xdata, 'b', "");
        GnomeSort(ref xdata);
        DisplayElements(ref xdata, 'a', "GnomeSort");
        Console.WriteLine("\n\n");

        MixDataUp(ref xdata, rdn);
        DisplayElements(ref xdata, 'b', "");
        InsertionSort(ref xdata);
        DisplayElements(ref xdata, 'a', "InsertionSort");
        Console.WriteLine("\n\n");

        MixDataUp(ref xdata, rdn);
        DisplayElements(ref xdata, 'b', "");
        QuickSort(ref xdata);
        DisplayElements(ref xdata, 'a', "QuickSort");
        Console.WriteLine("\n\n");

        MixDataUp(ref xdata, rdn);
        DisplayElements(ref xdata, 'b', "");
        ShellSort(ref xdata);
        DisplayElements(ref xdata, 'a', "ShellSort");
        Console.WriteLine("\n\n");

        MixDataUp(ref xdata, rdn);
        DisplayElements(ref xdata, 'b', "");
        SelectionSort(ref xdata);
        DisplayElements(ref xdata, 'a', "SelectionSort");
        Console.WriteLine("\n\n");

        MixDataUp(ref xdata, rdn);
        DisplayElements(ref xdata, 'b', "");
        MergeSort(ref xdata, 0, xdata.Length - 1);
        DisplayElements(ref xdata, 'a', "MergeSort");
        Console.WriteLine("\n\n");

        MixDataUp(ref xdata, rdn);
        DisplayElements(ref xdata, 'b', "");
        BucketSort(ref xdata);
        DisplayElements(ref xdata, 'a', "BucketSort");
        Console.WriteLine("\n\n");

        MixDataUp(ref xdata, rdn);
        DisplayElements(ref xdata, 'b', "");
        Heapsort(ref xdata);
        DisplayElements(ref xdata, 'a', "HeapSort");
        Console.WriteLine("\n\n");

        MixDataUp(ref xdata, rdn);
        DisplayElements(ref xdata, 'b', "");
        Count_Sort(ref xdata);
        DisplayElements(ref xdata, 'a', "CountSort");
        Console.WriteLine("\n\n");

        MixDataUp(ref xdata, rdn);
        DisplayElements(ref xdata, 'b', "");
        int bits = 4;
        RadixSort(ref xdata, bits);
        DisplayElements(ref xdata, 'a', "RadixSort");
        Console.WriteLine("\n\n");

        //The search tests that follow are divided into two steps
        //(1) Tries to find the 4th data entry in a randomized list. 
        //Since this data value always exist, the result will always be successful
        //(2) Tries to find a numerical value of 100 in a randomized list.
        //Since this data value is beyond the maximum
        //value that the random generator is setup 
        //to produce, the result will always fail.
        //This way all possible outcomes are fully checked.
        //Note that the linear search strategy
        //is the out method that accepts randomized data.
        //For all other searches, the data must be sorted first.

        Console.WriteLine("Search Algorithms Demo Code\n\n");

        MixDataUp(ref xdata, rdn); //Randomize data to be searched
        DisplayElements(ref xdata, 'b', ""); //Display random data

        Console.WriteLine("Using LINEAR SEARCH ALGORITHM " + 
                "to look for 4th data entry in randomized list");
        //Look for the 4th data entry in the list
        int location = LinearSearch(ref xdata, xdata[4]);
        if (location == -1)
            Console.WriteLine("Value was not found in list");
        else
            Console.WriteLine("Found it at location = {0}", location);
        location = LinearSearch(ref xdata, 100); //Look for the number 100 in the list.
        if (location == -1)
            Console.WriteLine("Value of 100 was not found in list");
        else
            Console.WriteLine("Value of 100 was found at at location = {0}", location);

        Console.WriteLine("\n\n");

        MixDataUp(ref xdata, rdn);
        DisplayElements(ref xdata, 'b', ""); //Display random data
        QuickSort(ref xdata);
        Console.WriteLine("Using INTERPOLATION SEARCH ALGORITHM " + 
                "to look for 4th data entry in randomized list");

        location = InterpolationSearch(ref xdata, xdata[4]);
        if (location == -1)
            Console.WriteLine("Value was not found in list");
        else
            Console.WriteLine("Found it at location = {0}", location);

        location = InterpolationSearch(ref xdata, 100);
        if (location == -1)
            Console.WriteLine("Value of 100 was not found in list");
        else
            Console.WriteLine("Value of 100 was found at at location = {0}", location);

        Console.WriteLine("\n\n");

        MixDataUp(ref xdata, rdn);
        DisplayElements(ref xdata, 'b', ""); //Display random data
        QuickSort(ref xdata);
        Console.WriteLine("Using BINARY SEARCH ALGORITHM to " + 
                          "look for 4th data entry in randomized list");

        location = BinSearch(ref xdata, xdata[4]);
        if (location == -1)
            Console.WriteLine("Value was not found in list");
        else
            Console.WriteLine("Found it at location = {0}", location);

        location = InterpolationSearch(ref xdata, 100);
        if (location == -1)
            Console.WriteLine("Value of 100 was not found in list");
        else
            Console.WriteLine("Value of 100 was found at at location = {0}", location);

        Console.WriteLine("\n\n");

        //The ArrayList collection in C# comes with its own built-in search algorithm.
        //And can be called up to perform a search as shown below.

        MixDataUp(ref xdata, rdn);
        DisplayElements(ref xdata, 'b', "");    //Display random data
        Console.WriteLine("Using the built-in BINARY " + 
                "SEARCH ALGORITHM in ArrayList data structure");
        ArrayList alist = new ArrayList();      //Set up an ArrayList object
        for (int i = 0; i < xdata.Length; i++)
            alist.Add(xdata[i]);                //and add some radomized data to it

        location = alist.BinarySearch(xdata[4]); //Call up its BinarySearch method
        if (location == -1)                     //and run the examples
            Console.WriteLine("Value was not found in list");
        else
            Console.WriteLine("Found it at location = {0}", location);

        location = alist.BinarySearch(100);
        if (location < 0)
            Console.WriteLine("Value was not found in list");
        else
            Console.WriteLine("Found it at location = {0}", location);

        Console.WriteLine("Testing to find the n-th largest " + 
                "value in a random array\n\nOriginal Data (method 1): \n");
        MixDataUp(ref xdata, rdn);
        DisplayElements(ref xdata, 'b', "");

        int nthMathIndex1 = 8;

        int nthMaxValue1 = NthLargest1(xdata, nthMathIndex1);

        Console.WriteLine("\nThe " + nthMathIndex1 + 
          " largest value in the array above is: " + 
          nthMaxValue1 + "\n");

        Console.WriteLine("Verifying result... \nFirst verify " + 
                          "that original data array is not changed.\n");
        DisplayElements(ref xdata, 'b', "");
        Console.WriteLine("\nThen sort the array and count the " + 
                "requested position from the largest value at the top\n");
        QuickSort(ref xdata);
        DisplayElements(ref xdata, 'a', "QuickSort");

        //////

        Console.WriteLine("\n\nTesting to find the n-th largest " + 
                "value in a random array\n\nOriginal Data (method 2): \n");
        MixDataUp(ref xdata, rdn);
        DisplayElements(ref xdata, 'b', "");

        int nthMathIndex2 = 4;

        int nthMinValue2 = NthLargest2(xdata, nthMathIndex2);

        Console.WriteLine("\nThe " + nthMathIndex2 + 
           " largest value in the array above is: " + 
           nthMinValue2 + "\n");

        Console.WriteLine("Verifying result... \nFirst verify " + 
                "that original data array is not changed.\n");
        DisplayElements(ref xdata, 'b', "");
        Console.WriteLine("\nThen sort the array and count the " + 
                "requested position from the smallest value at the bottom\n");
        QuickSort(ref xdata);
        DisplayElements(ref xdata, 'a', "QuickSort");

        Console.WriteLine("\n\nTesting to find the m-th smallest " + 
                "value in a random array\n\nOriginal Data (method 1): \n");
        MixDataUp(ref xdata, rdn);
        DisplayElements(ref xdata, 'b', "");

        int mthMathIndex1 = 3;

        int mthMinValue1 = MthSmallest1(xdata, mthMathIndex1);

        Console.WriteLine("\nThe " + mthMathIndex1 + 
                " smallest value in the array above is: " + 
                mthMinValue1 + "\n");

        Console.WriteLine("Verifying result... \nFirst verify " + 
                "that original data array is not changed.\n");
        DisplayElements(ref xdata, 'b', "");
        Console.WriteLine("\nThen sort the array and count the " + 
                "requested position from the smallest value at the bottom\n");
        QuickSort(ref xdata);
        DisplayElements(ref xdata, 'a', "QuickSort");

        Console.WriteLine("\n\nTesting to find the m-th smallest " + 
                "value in a random array\n\nOriginal Data (method 2): \n");
        MixDataUp(ref xdata, rdn);
        DisplayElements(ref xdata, 'b', "");

        int mthMathIndex2 = 3;

        int mthMinValue2 = MthSmallest2(xdata, mthMathIndex2);

        Console.WriteLine("\nThe " + mthMathIndex2 + 
           " smallest value in the array above is: " + 
           mthMinValue2 + "\n");

        Console.WriteLine("Verifying result... \nFirst " + 
                "verify that original data array is not changed.\n");
        DisplayElements(ref xdata, 'b', "");
        Console.WriteLine("\nThen sort the array and count the " + 
                "requested position from the smallest value at the bottom\n");
        QuickSort(ref xdata);
        DisplayElements(ref xdata, 'a', "QuickSort");

        Console.WriteLine("\n\nTesting sorting utitlities\n");
        int[] sortedInts = new int[] { 1, 5, 20, 50 };
        int[] unsortedInts = new int[] { 35, 2, 56, 1 };
        int[] reversedInts = new int[] { 10, 9, 8, 7 };
        string[] sortedStrings = new string[] { "monkey", "duck", "bird" };
        string[] unsortedStrings = new string[] { "duck", "monkey", "dog" };
        string[] reversedStrings = new string[] { "dog", "duck", "monkey" };

        Console.WriteLine(IsSorted(sortedInts));                // True
        Console.WriteLine(IsSortedDescending(sortedInts));      // False
        Console.WriteLine(IsSorted(unsortedInts));              // False
        Console.WriteLine(IsSortedDescending(unsortedInts));    // False
        Console.WriteLine(IsSorted(reversedInts));              // False
        Console.WriteLine(IsSortedDescending(reversedInts));    // True
        Console.WriteLine(IsSorted(sortedStrings));             // True
        Console.WriteLine(IsSortedDescending(sortedStrings));   // False
        Console.WriteLine(IsSorted(unsortedStrings));           // False
        Console.WriteLine(IsSortedDescending(unsortedStrings)); // False
        Console.WriteLine(IsSorted(reversedStrings));           // False
        Console.WriteLine(IsSortedDescending(reversedStrings)); // True
        Console.ReadLine();

        Console.WriteLine("\n\nTesting Conversion from List to Array\n");
        List<string> myList = new List<string>();
        myList.Add("dog");
        myList.Add("cat");
        myList.Add("duck");
        myList.Add("monkey");
        myList.Add("bird");
        string[] myString = myList.ToArray();
        foreach (string s in myString)
            Console.WriteLine(s);

        Console.WriteLine("\n\nTesting Conversion from Array to List\n");
        string[] str = new string[] { "duck", "cat", "dog", "monkey", "bird" };
        List<string> myOtherList = new List<string>(str);
        myOtherList = str.ToList();
        foreach (string s in myOtherList)
            Console.WriteLine(s);

        Console.ReadLine();
    }
}

The single most important purpose of learning algorithms is to be able to code them to work with large amounts of data to solve problems. The code shown above was not coded using data parallelism. Perhaps it could be an exercise to the reader to find parallelizable "hotspots" and use the appropriate Task Parallel Library construct on them.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)