Язык программирования C#

Сортировка

1. Сортировка пузырьком. Дан массив A размера N. Упорядочить его по возрастанию методом сортировки простым обменом («пузырьковой» сортировкой): просматривать массив, сравнивая его соседние элементы (a[0] и a[1], a[1] и a[2] и т. д.) и меняя их местами, если левый элемент пары больше правого; повторить описанные действия N − 1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает - массив отсортирован. Учесть, что при каждом просмотре количество анализируемых пар можно уменьшить на 1.
   Указание 1. В задаче удобно использовать метод Swap(ref int a, ref int b) из лабораторной работы №1.
   Указание 2. Все методы сортировки принимают в качестве параметра массив целых чисел (и только его).
   
2. Сортировка выбором. Дан массив размера N. Упорядочить его по возрастанию методом сортировки выбором: найти максимальный элемент массива и поменять его местами с последним (N-1) элементом; выполнить описанные действия N − 1 раз, каждый раз уменьшая на 1 количество анализируемых элементов.
   Указание 1 В задаче удобно использовать метод Swap(ref int a, ref int b) из лабораторной работы №1.
   Указание 2 Создайте вспомогательный метод static int MaxIdx(int[] array, int n), который возвращает индекс наибольшего элемента, индекс которого меньше n
3. Сортировка выбором. Дан массив размера N. Упорядочить его по возрастанию методом сортировки выбором: найти минимальный элемент массива и поменять его местами с первым элементом в неотсортированной части массива; выполнить описанные действия N − 1 раз, каждый раз уменьшая на 1 количество анализируемых элементов.
   Указание Создайте вспомогательный метод static int MinIdx(int[] array, int n), который возвращает индекс наибольшего элемента, индекс которого больше n
4. Создать вспомогательный метод static void MakeItSorted(int[] array, int n) Дан массив, элементы которого с нулевого по элемент с индексом n-1, упорядочены по возрастанию, а элемент с индексом n нарушает упорядоченность. Сделать массив упорядоченным, переместив n-й элемент на новую позицию
   Указание В задаче удобно использовать метод Swap(ref int a, ref int b) в цикле.
5. Сортировка вставками. Дан массив A размера N. Упорядочить его по возрастанию методом сортировки вставками:
   • Массив, состоящий из одного элемента - упорядоченный.
   • Рассмотрим первые два элемента массива и поменяем их местами таким образом, чтобы первые два элемента были упорядочены.
   • Предположим, что n-1 элементов массива упорядочены. Переместим n-й элемент массива таким образом, чтобы n элементов массива образовывали упорядоченную последовательность.
   Реализуем алгоритм при помощи одного цикла, на каждой итерации которого происходит вызов метода MakeItSorted

Замер производительности метода, делегаты

1. Создайте метод static int[] RandomIntArray(int size = 10, int min = -10, int max = 10) создающий массив, заполненный случайными целыми числами в диапазоне от min до max. (или сразу возьмите готовый из лабораторной №3)
2. Объявите делегат (делегаты - это указатели на методы). Наш делегат должен указывать на метод, который принимает массив целых чисел и не возвращает никакого результата

   delegate void SortingMethod(int[] array);
   

3. Создать метод

   private static long CheckPerformance(int[] a, SortingMethod sortingMethod)
   

   который замеряет производительность метода и возвращает время его работы в миллисекундах (long - длинное целое число).
   Указание Используем объект типа Stopwatch. Для инициализации нового объекта используем конструкцию

           var watch = Stopwatch.StartNew();
   

   или

           Stopwatch watch = new Stopwatch();
           watch.Start();
   

   Для того, чтобы вызвать сортирующий метод, нужно указать имя параметра типа SortingMethod. Вызов делегата производится подобно вызову метода. Для остановки замера времени используем метод Stop(), для того, чтобы найти время в миллисекундах - свойство ElapsedMilliseconds.
4. Создайте в методе Main массив делегатов

   SortingMethod[] methods = {/* добавьте сюда названия всех своих методов сортировки через запятую*/};
   

   Создайте целую переменную size - размер массива случайных целых чисел. В цикле по элементам массива methods делайте следующее
   • создать array - массив случайных целых чисел размера size;
   • замерить время работы метода сортировки при помощи CheckPerformance
   • вывести на консоль сообщение вида

     Для метода BubbleSort время сортировки массива из 10000 элементов - 1052 ms.
     

     (для того, чтобы из переменной-делегата получить название метода, используем свойства Method и Name, например methods[i].Method.Name)
   Запустите программу для случаев size = 100; size = 1000; и size = 10000;