// lists/strings problem 16

​

using System;

using System.Collections.Generic;

​

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:

                theList = MergeSort(theList);

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

                DisplayList(theList);

                break;

            case 4:

                theList = QuickSort(theList);

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

                DisplayList(theList);

                break;

            case 5:

                theList = StoogeSort(theList);

                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 List<int> MergeSort(List<int> list) {

        if (list.Count <= 1) {

            return list;

        }

        int middleIndex = (list.Count) / 2;

        List<int> left = new List<int>(new int[middleIndex]);

        List<int> right = new List<int>(new int[list.Count - middleIndex]);

​

        Array.Copy(list.ToArray(), left.ToArray(), middleIndex);

        Array.Copy(list.ToArray(), middleIndex, right.ToArray(), 0, right.Count);

​

        // 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);

    }

​

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

        List<int> leftList = left;

        List<int> rightList = right;

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

​

        // while the sublists are not empty, merge them repeatedly to produce new sublists 

        // until there is only 1 sublist remaining. this will be the sorted list

        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);

            }

        }

        return resultList;

    }

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

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

        return list;    

    }

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

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

        return list;    

    }

}