// lists/strings problem 16

​

using System;

using System.Collections.Generic;

using System.Linq;

​

public class Program

{

    private static List<int> theList;

    private static Random r = new Random();

    public static void Main()

    {

        theList = new List<int>();

        for(int i = 0; i < 20; i++) {

            theList.Add(r.Next(1, 101));    

        }

        Console.Write("List contents: ");

        DisplayList(theList);

        int option = MainMenu();

        switch(option) {

            case 1:

                theList = SelectionSort(theList);

                Console.Write("List after SelectionSort(): " );

                DisplayList(theList);

                break;

            case 2:

                theList = InsertionSort(theList);

                Console.Write("List after InsertionSort(): " );

                DisplayList(theList);

                break;

            case 3:

                int[] listArray = new int[20];

                listArray = MergeSort(theList.ToArray());

                theList = listArray.ToList();

                Console.Write("List after MergeSort(): " );

                DisplayList(theList);

                break;

            case 4:

                theList = QuickSort(theList, 0, theList.Count() - 1);

                Console.Write("List after QuickSort(): " );

                DisplayList(theList);

                break;

            case 5:

                theList = StoogeSort(theList, 0, theList.Count - 1);

                Console.Write("List after StoogeSort(): " );

                DisplayList(theList);

                break;

        }

    }

    // MainMenu() method -- displays a menu that asks the user to choose with sort method they want to use

    public static int MainMenu() {

        int option;

        Console.WriteLine("\n\nChoose an option");

        Console.WriteLine("----------------");

        Console.WriteLine("[1] SelectionSort()");

        Console.WriteLine("[2] InsertionSort()");

        Console.WriteLine("[3] MergeSort()");

        Console.WriteLine("[4] QuickSort()");

        Console.WriteLine("[5] StoogeSort()");

        Console.WriteLine("----------------");

        Console.Write("Enter choice: ");

        option = Convert.ToInt32(Console.ReadLine());

        while(option < 1 || option > 5) {

            Console.WriteLine("Not a valid choice");

            Console.Write("Enter choice: ");

            option = Convert.ToInt32(Console.ReadLine());

        }

        return option;

    }

    // DisplayList() method -- displays the elements inside a list

    public static void DisplayList(List<int> list) {

        foreach(int item in list) {

            Console.Write(item + " ");  

        }

    }

    // SelectionSort() method -- sorts the elements of a list

    public static List<int> SelectionSort(List<int> list) {

        int pos_min, temp;

        for (int i = 0; i < list.Count - 1; i++) {

            pos_min = i;

            for (int j = i + 1; j < list.Count; j++) {

                if (list[j] < list[pos_min]) {

                    pos_min = j;

                }                                          

            }

            if (pos_min != i) {

                temp = list[i];

                list[i] = list[pos_min];

                list[pos_min] = temp;

            }

        }

        return list;

    }

    // InsertionSort() method -- sorts the elements of a list

    public static List<int> InsertionSort(List<int> list) {

        int temp, j;

        for (int i = 1; i < list.Count; i++) {

            temp = list[i];

            j = i - 1;

            while (j >= 0 && list[j] > temp) {

                list[j + 1] = list[j];

                j--;

            }

            list[j + 1] = temp;

        }

        return list;    

    }

    // MergeSort() method -- sorts the elements of a list

    public static int[] MergeSort(int[] array) {

        if (array.Length <= 1) {

            return array;

        }

​

        int middleIndex = (array.Length) / 2;

        int[] left = new int[middleIndex];

        int[] right = new int[array.Length - middleIndex];

​

        Array.Copy(array, left, middleIndex);

        Array.Copy(array, middleIndex, right, 0, right.Length);

​

        // recursively call MergeSort() to further split each sublist until sublist size is 1.

        left = MergeSort(left);

        right = MergeSort(right);

​

        // merge the sublists returned from prior calls to MergeSort() and return the resulting merged sublist.

        return Merge(left, right);

    }

​

    // Merge() method --  does the background sorting algorithm for the MergeSort() method

    public static int[] Merge(int[] left, int[] right) {

        // convert the input arrays to lists

        List<int> leftList = left.OfType<int>().ToList();

        List<int> rightList = right.OfType<int>().ToList();

        List<int> resultList = new List<int>();

​

        while (leftList.Count > 0 || rightList.Count > 0) {

            if (leftList.Count > 0 && rightList.Count > 0) {

                if (leftList[0] <= rightList[0]) {

                    resultList.Add(leftList[0]);

                    leftList.RemoveAt(0);

                }

                else {

                    resultList.Add(rightList[0]);

                    rightList.RemoveAt(0);

                }

            }

            else if (leftList.Count > 0) {

                resultList.Add(leftList[0]);

                leftList.RemoveAt(0);

            }

            else if (rightList.Count > 0) {

                resultList.Add(rightList[0]);

                rightList.RemoveAt(0);

            }

        }

        int[] result = resultList.ToArray();

        return result;

    }

    // QuickSort() method -- sorts the elements of a list

    public static List<int> QuickSort(List<int> list, int left, int right) {

        int i = left;

        int j = right;

        IComparable pivot = list[(left + right) / 2];

        while (i <= j) {

            while (list[i].CompareTo(pivot) < 0) {

                i++;

            }           

            while (list[j].CompareTo(pivot) > 0) {

                j--;

            }       

            if (i <= j) {

                IComparable tmp = list[i];

                list[i] = list[j];

                list[j] = Convert.ToInt32(tmp);

                i++;

                j--;

            }

        }

        // recursive calls

        if (left < j) {

            QuickSort(list, left, j);

        }       

        if (i < right) {

            QuickSort(list, i, right);

        }

        return list;

    }

    // StoogeSort() method -- sorts the elements of a list

    private static List<T> StoogeSort<T>(List<T> list, int i, int j) where T : IComparable {

        if (list[j].CompareTo(list[i]) < 0) {

            T tmp = list[i];

            list[i] = list[j];

            list[j] = tmp;

        }

        if (j - i > 1) {

            int t = (j - i + 1) / 3;

            StoogeSort(list, i, j - t);

            StoogeSort(list, i + t, j);

            StoogeSort(list, i, j - t);

        }

        return list;

    }

}