using System;

using System.Collections.Generic;

public class Program

{

    //The class SortUtility should be ENCAPSULATED.  It should give you want you need to spit out the sorted numbers, but not interfere with the world outside itself.  That's how I see it, at least.

​

    public static void Main()

    {

        Console.WriteLine("Hello World");

        //I could have saved myself a lot of trouble by never using that generic collection.  Maybe?  For consideration.

        int[] values = {9, 3, 5, 8, 20, 300, 2, 2, 0, -32, 32};

        List<int> testValuesToSort = new List<int>(values);

        SortUtility test1 = new SortUtility(testValuesToSort, ESortMethods.Bubble);

        SortUtility test2 = new SortUtility(testValuesToSort, ESortMethods.Insert);

        test1.WriteToConsole();

        Console.WriteLine("Goodbye.");

    }

}

​

public enum ESortMethods {None, Bubble, Insert, Select, Shell, Merge, Heap, Quick, Quick3}

​

public class SortUtility

{

    //Both of these need to stay private, to ensure nothing in them is accidentally changed.  See properties for these fields, below.

    private List<int> inputList;

    private List<int> outputList;

    public List<int> InputList

    {

        get { return inputList; }

        set 

        {

            //If the user overwrites the input, then we must recalculate the output.

            inputList = value;

            outputList = sortHandler(inputList);

        }

    }

    public List<int> OutputList

    {

        get { return outputList; }

        private set { outputList = value; }

    }

    public delegate List<int> Sorter (List<int> listToSort);

    Sorter sortHandler;

    //START OF METHODS FOR THE Sorter DELEGATE.

    //Method used for the default case.  To make it clear what would happen if you don't provide a sortMethod.

    private List<int> noSort (List<int> listToSort) {return listToSort;}

    private List<int> bubbleSort (List<int> listToSort)

    {

        /*

            The bubble sort algorithm - it is very simple, however can be very inefficent.

            In large, very disorganized collections, it could take a prohibitively long time to run.

            However, it's fine for small lists of things.

        */

        int[] intList = listToSort.ToArray();

        /*

        HOW DOES A BUBBLE SORT WORK?

        If we interate through the list without having to do a swap, then we've gotten a clean pass through.  

        If we've passed through the entire list, without having to do a swap, then the list is sorted.

        If the list is sorted, then we are finished, and can return the generated list.

        */

        bool cleanPassThrough;

        do

        {

            cleanPassThrough = true;  //Default this to true.  We assume the list is sorted, unless we find otherwise.

            //POSSIBLE ***INFINITE LOOP*** BUG HERE:  If we never enter the FOR statement (maybe because the array to sort is too small?), then we could get a false result.

            /*NOTE:  The condition for continuing to loop is:

                iterator < intList.Length - 1;

            Why?  Because we compare an item, with the item that comes AFTER it.

            There is no item AFTER the last item in the list.  So we need to stop looping through the list, one item before the end of the collection.

            */

            for ( int iterator = 0; iterator < intList.Length - 1; iterator++ ) 

            { 

                int itemA = intList[iterator];

                int itemB = intList[iterator + 1];

                if (itemA > itemB) 

                {   

                    //Here, we swap the two items.

                    cleanPassThrough = false;  //If you've entered this block, then there will be at least one more run through.  (This is inefficent, but hey, welcome to bubble sort.)

                    int tempHoldingSpot = itemA;

                    itemA = itemB;

                    itemB = tempHoldingSpot;

                    intList[iterator] = itemA;

                    intList[iterator + 1] = itemB;

                }

            }

        } while (cleanPassThrough == false);

        /*  DEBUG CODE --- MAY BE REMOVED

        Console.WriteLine("Within the BubbleSort() method, the readout of intList:");

        foreach (int intItem in intList)

        {

            Console.Write(intItem.ToString());

            Console.Write("  ---  ");

        } Console.WriteLine("");

        */ 

        //  END OF DEBUG CODE --- MAY BE REMOVED

        return new List<int>(intList);

    }

    private List<int> insertionSort (List<int> listToSort)

    {

        int arrayLength = listToSort.Count + 1;

        int[] arrayToSort = new int[arrayLength];

        int[] inputArray = listToSort.ToArray();  //This must be able to be eliminated, somehow.  We never use this array again.  

        //We just need to create an array with a size one larger than the input.  Declaring this is a waste of space.  You've doubled the amount of memory being used, which does matter for large data sets.

        //Figure out how to do without.  I don't believe you can resize an array in C#, without re-initializing everything and copying it over.

        //I tried to do the following:

        /*      

            create an array of size N + 1 (need the extra space for shifting).  

            However when I call List<T>.ToArray(), that returns a new array, with size N (missing the extra space needed for shifting).

            The value returned by ToArray() overwrites the reference to the location in memory to the properly sized array.

            ToArray() is the problem.  But what do you use instead?

            I need a function in System.Array that accepts as a parameter, a populated array, and only adds it to an existing array.

                Array.CopyTo() or Array.Copy()

            While this isn't wrong, we still have duplicitious data.  The parameter listToSort, and the array we create out of it, both hold the same data.

            If you wanted to be as memory efficient as possible, you'd want to receive the data here as an array.  

            There's no sense (in this case) of creating a method that demands a parameter that it immediately converts.

​

            SortUtility (this entire package) should start out by dealing with arrays, rather than List<T>

            I don't know of any sort algorithms (yet) that would benefit by receiving the data in that type of collection.

        */

        for (int i = 0; i < inputArray.Length; i++)

        {

            arrayToSort[i] = inputArray[i];

        }

        //Attempt 1:

        for (int i = 1; i < arrayToSort.Length; i++)

        {

            if (arrayToSort[i] > arrayToSort[i - 1]) 

            {

                //Do nothing

            } else if (arrayToSort[i] < arrayToSort[i - 1])

            {

                int movedItem = arrayToSort[i];

                for (int backwardsCounter = i; movedItem > 0; backwardsCounter--)  

                {

                    //arghhhh I need to get back to work

                }

            }

        }

        //REPLACE THE FOLLOWING WITH A REAL LIST.

        return new List<int>();

    }

    //END OF METHODS FOR THE Sorter DELEGATE.

    public void WriteToConsole() 

    { 

        Console.WriteLine("Printout of UNSORTED Input (original): ");

        foreach (int intItem in InputList)

        {

            Console.Write(intItem.ToString());

            Console.Write("  ---  ");

        } Console.WriteLine("");

        Console.WriteLine("Printout of SORTED collection: ");

        foreach (int intItem in OutputList)

        {

            Console.Write(intItem.ToString());

            Console.Write("  ---  ");

        } Console.WriteLine("");

    }

    //CONSTRUCTOR

    public SortUtility(List<int> input, ESortMethods sortMethod)

    {

        inputList = new List<int>(input);  //Create a copy of the list as received so that we can reference it as needed.

        switch (sortMethod)

        {

            case ESortMethods.Bubble:

                sortHandler = bubbleSort;

                break;

            case ESortMethods.Insert:

                sortHandler = insertionSort;

                break;

            case ESortMethods.None:  

                //Intentionally left blank - control will fall through to default case.

            default:

                sortHandler = noSort;

                break;

        }

        OutputList = sortHandler(input);

    }

}