using System;

using System.Collections.Generic;

using System.Linq;

using System.Reflection;

using System.Diagnostics;

​

[AttributeUsage(System.AttributeTargets.Method, AllowMultiple = false)]

class SortableAttribute : System.Attribute

{

}

​

static class ArrayUtility

{

    private static Random random = new Random();

    public static int[] GetNumbers(int size, int rangeStart, int rangeEnd) => [..Enumerable.Range(0, size).Select(_ => random.Next(rangeStart, rangeEnd))];

    public static void PrintNumbers(int[] numbers)

    {

        Console.WriteLine();

        for (int i = 0, iLength = numbers.Length; i < iLength; i++)

        {

            Console.Write($"{numbers[i]}".PadRight(5, ' '));

        }

    }

}

​

static class Sorting

{

    [Sortable]

    public static void BubbleSort(int[] numbers)

    {

        int temporary;

        bool isSorted;

        for (int i = 0, iLength = numbers.Length; i < iLength; i++)

        {

            isSorted = true;

            for (int j = 0, jLength = numbers.Length - i - 1; j < jLength; j++)

            {

                if (numbers[j] > numbers[j + 1])

                {

                    temporary = numbers[j];

                    numbers[j] = numbers[j + 1];

                    numbers[j + 1] = temporary;

                    isSorted = false;

                }

            }

​

            if (isSorted)

            {

                break;

            }

        }

    }

​

    [Sortable]

    public static void SelectionSort(int[] numbers)

    {

        int minimum, minimumIndex;

        for (int i = 0, iLength = numbers.Length; i < iLength; i++)

        {

            minimum = numbers[i];

            minimumIndex = i;

            for (int j = i + 1, jLength = numbers.Length; j < jLength; j++)

            {

                if (numbers[j] < minimum)

                {

                    minimum = numbers[j];

                    minimumIndex = j;

                }

            }

​

            numbers[minimumIndex] = numbers[i];

            numbers[i] = minimum;

        }

    }

​

    [Sortable]

    public static void InsertionSort(int[] numbers)

    {

        int key;

        for (int i = 1, iLength = numbers.Length; i < iLength; i++)

        {

            key = numbers[i];

            for (int j = i - 1; j >= 0; j--)

            {

                if (numbers[j] < numbers[j + 1])

                {

                    break;

                }

​

                key = numbers[j];

                numbers[j] = numbers[j + 1];

                numbers[j + 1] = key;

            }

        }

    }

​

    [Sortable]

    public static void MergeSort(int[] numbers)

    {

        static void MergeSort(int[] numbers, int start, int end)

        {

            if (start < end)

            {

                int pivot = start + (end - start) / 2;

                MergeSort(numbers, start, pivot);

                MergeSort(numbers, pivot + 1, end);

                Merge(numbers, start, pivot, end);

            }

        }

​

        static void Merge(int[] numbers, int start, int pivot, int end)

        {

            int iLength = pivot - start + 1;

            int[] left = new int[iLength];

            int i = 0;

            for (; i < iLength; i++)

            {

                left[i] = numbers[start + i];

            }

​

            int jLength = end - pivot;

            int[] right = new int[jLength];

            int j = 0;

            for (; j < jLength; j++)

            {

                right[j] = numbers[pivot + 1 + j];

            }

​

            i = 0;

            j = 0;

            int k = start;

            while (i < iLength && j < jLength)

            {

                if (left[i] <= right[j])

                {

                    numbers[k] = left[i];

                    i++;

                }

                else

                {

                    numbers[k] = right[j];

                    j++;

                }

​

                k++;

            }

​

            while (i < iLength)

            {

                numbers[k] = left[i];

                i++;

                k++;

            }

​

            while (j < jLength)

            {

                numbers[k] = right[j];

                j++;

                k++;

            }

        }

​

        MergeSort(numbers, 0, numbers.Length - 1);

    }

​

    [Sortable]

    public static void QuickSort(int[] array)

    {

        int Partition(int[] array, int left, int right)

        {

            int pivot = array[right];

            int store = left - 1;

            int temporary;

            for (int i = left; i < right; i++)

            {

                if (array[i] <= pivot)

                {

                    store++;

                    temporary = array[store];

                    array[store] = array[i];

                    array[i] = temporary;

                }

            }

​

            temporary = array[store + 1];

            array[store + 1] = pivot;

            array[right] = temporary;

            return store + 1;

        }

​

        void QuickSort(int[] array, int left, int right)

        {

            if (left < right)

            {

                int pivot = Partition(array, left, right);

                QuickSort(array, left, pivot - 1);

                QuickSort(array, pivot + 1, right);

            }

        }

​

        QuickSort(array, 0, array.Length - 1);

    }

}

​

static class SortRunner

{

    private const string ArrayFormatter = "\n\n{0}";

    private const string ElapsedFormatter = "elapsed = {0}\n";

    private static Stopwatch? stopwatch;

    private static readonly int[] sealedNumbers = ArrayUtility.GetNumbers(20, -20, 20);

    public static void RunSort(Action<int[]> sortingFunction)

    {

        Console.WriteLine(ArrayFormatter, sortingFunction.Method.Name);

        int[] numbers = [..sealedNumbers];

        stopwatch = Stopwatch.StartNew();

        sortingFunction(numbers);

        stopwatch.Stop();

        ArrayUtility.PrintNumbers(numbers);

        Console.WriteLine(ElapsedFormatter, stopwatch.Elapsed);

    }

}

​

public class Program

{

    private static readonly IEnumerator<Action<int[]>> algorithms = typeof(Sorting).GetMethods().Where(_ => _.IsDefined(typeof(SortableAttribute))).Select(method => method.CreateDelegate<Action<int[]>>()).GetEnumerator();

    static void Main()

    {

        while (algorithms.MoveNext())

        {

            SortRunner.RunSort(algorithms.Current);

        }

    }

}