Домашнее задание №3

В качестве домашнего задания №1 мне сдали две совершенно одинаковые работы. Если плагиат повторится, у обоих будет оценка 0.

Сортировка

  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
Продемонстрируйте в методе Main() работу каждого из методов сортировки.

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

  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;