C#. Разработка обобщенного класса, который реализует алгоритм сортировки выбором на языке C#. Контрольная работа




Разработка обобщенного класса, который реализует алгоритм сортировки выбором на языке C#. Контрольная работа

В данной теме описывается реализация обобщенного класса на языке C#, который содержит средства реализующие алгоритм сортировки выбором.
Перед использованием данной темы рекомендуется ознакомиться с теоретическими особенностями алгоритма в следующей теме:


Содержание


Поиск на других ресурсах:

Условие задачи

Разработать обобщенный класс SortSelection<T>, который реализует алгоритм сортировки выбором. Продемонстрировать работу методов класса.

 

Выполнение

1. Создание проекта. Классы SortSelection<T> и Program. Интерфейс IComparable<T>

Разработка класса выполняется в системе Microsoft Visual Studio — 2019 по шаблону приложения C# — Console Application. Предварительно формируется текст двух классов:

  • обобщенного класса SortSelection<T>, который есть решением данной задачи;
  • класса Program, в котором будет протестирована работа класса SortSelection<T>.

Начальный код программы следующий

// Разработка класса, который реализует алгоритм сортировки выбором
using System;
using static System.Console;

namespace ConsoleApp10
{
  // Обобщенный класс SortSelection<T> - реализует алгоритм сортировки выбором.
  // Чтобы сравнивать значения, нужно реализовать интерфейс IComparable<T>.
  class SortSelection<T> where T:IComparable<T>
  {

  }

  // Класс Program - тестирует работу класу SortSelection<T>
  class Program
  {
    static void Main(string[] args)
    {

    }
  }
}

Как видно из кода, класс SortSelection<T> реализует обобщенный интерфейс IComparable<T>

...

class SortSelection<T> where T:IComparable<T>
{

}

...

Интерфейс обеспечивает так называемую типовую безопасность при сравнении значений некоторого обобщенного типа T. В интерфейсе объявлен метод CompareTo()

int CompareTo()

который используется в нашей программе в методах Sort() и SortRange() (смотрите п.п. 2.5, 2.6) для сравнения двух значений некоторого типа T.
Если не выполнить реализацию интерфейса IComparable<T> в классе SortSelection<T> и написать объявление класса следующим образом

...

class SortSelection<T>
{

}

...

тогда невозможно будет сравнивать значение обобщенного типа T, и методы сортировки не удастся реализовать. В этом случае обычные операции сравнения <, >, == не обеспечивают типовой безопасности.

 

2. Разработка класса SortSelection<T>
2.1. Ввод внутренних переменных класса

В классе SortSelection<T> в разделе private вводится внутренняя переменная A – массив обрабатываемых чисел.

...

// Обобщенный класс SortSelection<T> - реализует алгоритм сортировки выбором
class SortSelection<T>
{
  // Одномерный массив с данными, которые будут сортироваться
  private T[] A;
}

...

 

2.2. Конструкторы класса

На этом этапе в текст класса SortSelection<T> вводятся три конструктора, инициализирующие внутренние данные класса (массив A).

// Конструкторы.
// Конструктор без параметров
public SortSelection()
{
  A = null;
}

// Конструктор, который получает внешний массив типа T[]
public SortSelection(T[] A)
{
  // Сделать копию с помощью метода Clone()
  this.A = (T[])A.Clone();
}

// Конструктор, который получает входным экземпляр класса SortSelection<T>
public SortSelection(SortSelection<T> obj)
{
  A = (T[])obj.A.Clone();
}

 

2.3. Методы доступа Get(), Set()

Для доступа к внутреннему массиву A необходимо реализовать соответствующие методы доступа Get(), Set(). Следует заметить, что в методах доступа используется копирование массива с использованием метода Clone().

Метод Clone() имеет следующие особенности:

  • метод выполняет копию массива с выделением памяти в другой области. Таким образом массив экземпляра A и внешний массив размещаются в разных участках памяти. Если вместо использования метода Clone() (A=_A.Clone()) использовать простое присваивание ссылок (например A = _A), тогда внешний и внутренний массивы будут указывать на один и тот же участок памяти. Это может привести к невидимым ошибкам, если изменения во внешнем массиве будут влиять на внутренний (и наоборот), что есть нежелательно;
  • метод объявлен в классе System.Array, что есть базовым для всех массивов, объявленных в программе. Поэтому, этот метод доступен в программе.
// Методы доступа.
// Получить копию массива A
public T[] Get()
{
  return (T[])A.Clone();
}

// Установить новое значение массива
public void Set(T[] _A)
{
  A = (T[])_A.Clone();
}

 

2.4. Метод Sort(). Сортировка всего массива. Метод CompareTo()

Основным методом класса есть метод Sort(), в котором осуществляется сортировка всего массива. Особенность этого метода состоит в том, что для сравнения двух значений обобщенного типа T используется метод CompareTo(), который объявлен в интерфейсе IComparable<T>.

Метод CompareTo() имеет следующее объявление:

int CompareTo(T other);

здесь other – экземпляр (объект) обобщенного типа T.

Метод сравнивает текущий экземпляр с другим объектом такого же типа и возвращает целое число. Это число определяет, следует ли текущий экземпляр перед, после или находится в этой самой позиции в порядке сортировки в вравнении с объектом other. Если метод возвращает число <0, то значение текущего экземпляра следует перед значением объекта other (меньше). Если метод возвращает число ==0, то значения эквивалентны с точки зрения порядка сортировки. Если метод возвращает число >0, то значение текущего экземпляра следует после значения объекта other (больше).

// Методы сортировки
// Метод, который сортирует весь массив.
// Параметр order задает порядок сортировки,
// - если order=true, то отсортировать в порядке возрастания;
// - если order=false, то отсортировать в порядке убывания.
public void Sort(bool order)
{
  int i, j, k;
  T t;

  for (i = 0; i < A.Length; i++) // i - номер шага
  {
    k = i;
    t = A[i];

    // Цикл поиска наименьшего (наибольшего) элемента
    for (j = i + 1; j < A.Length; j++)
      if (order)
      {
        // Поиск наименьшего элемента.
        // Для сравнения используется метод CompareTo(),
        // который объявлен в интерфейсе IComparable<T>.
        // Метод возвращает значение:
        // - меньше 0, если текущий экземпляр следует перед (меньше) екземляром-параметром;
        // - больше 0, если текущий экземпляр следует после экземпляра-параметра;
        // - равно 0, если значения экземпляров равны.
        if (A[j].CompareTo(t)<0)
        {
          k = j;
          t = A[j];
        }
      }
      else
      {
        // Поиск наибольшего элемента
        if (A[j].CompareTo(t) > 0)
        {
          k = j;
          t = A[j];
        }
      }

    A[k] = A[i];
    A[i] = t;
  }
}

 

2.5. Метод SortRange(). Сортировка массива в заданном диапазоне

Модификацией метода Sort() есть метод SortRange(), позволяющий отсортировать не весь массив, а его часть в указанном диапазоне.

// Метод, который реализует алгоритм сортировки выбором в указанном диапазоне [pos1, pos2-1]
// Параметры:
// - order - порядок сортировки (true-по возрастанию, false-по убыванию);
// - pos1 - нижняя граница индекса в массиве включительно;
// - pos2 - верхняя граница индекса - исключительно.
// Если сортировка состоялась успешно, функция возвращает true, иначе - false.
public bool SortRange(bool order, int pos1, int pos2)
{

  // Проверка, адекватны ли значения pos1, pos2
  if (pos1 >= pos2) return false;
  if ((pos1 < 0) || (pos1 >= A.Length)) return false;
  if ((pos2 < 0) || (pos2 > A.Length)) return false;

  // Если все в порядке, то отсортировать массив
  int i, j, k;
  T t;

  for (i = pos1; i < pos2; i++) // i - номер шага
  {
    k = i;
    t = A[i];

    // Цикл поиска наименьшего (наибольшего) элемента
    for (j = i + 1; j < pos2; j++)
      if (order)
      {
        // Поиск наименьшего элемента
        if (A[j].CompareTo(t) < 0)
        {
          k = j;
          t = A[j];
        }
      }
      else
      {
        // Поиск наибольшего элемента
        if (A[j].CompareTo(t) > 0)
        {
          k = j;
          t = A[j];
        }
      }

    A[k] = A[i];
    A[i] = t;
  }

  return true;
}

 

2.6. Метод Print(). Вывод массива

Метод Print() выводит содержимое внутреннего массива A на экран. Метод используется с целью тестирования.

// Вывод внутреннего массива на экран
public void Print(string comment)
{
  WriteLine(comment);
  for (int i = 0; i < A.Length; i++)
    Write("{0} ", A[i]);
  WriteLine();
}

 

3. Разработка класса Program

Класс Program содержит статическую функцию main(), в которой продемонстрировано использование методов класса SortSelection<T>.

// Класс Program - тестирует работу класса SortSelection<T>
class Program
{
  static void Main(string[] args)
  {
    // 1. Работа с массивом типа int
    // 1.1. Объявить массив целых чисел
    int[] AI = { 3, 5, -1, 2, -4 };

    // 1.2. Создать экземпляр на основании массива AI
    SortSelection<int> objInt1 = new SortSelection<int>(AI);
    objInt1.Print("objInt1 before sorting");

    // 1.3. Отсортировать массив objInt1
    objInt1.Sort(true);
    objInt1.Print("objInt1 after sorting");

    // 1.4. Отсортировать в указанном диапазоне [1, 2]
    objInt1.SortRange(false, 1, 3);
    objInt1.Print("objInt1.SortRange(false, 1, 3):");

    // 2. Работа с массивом типа string
    string[] AS =
    {
      "abcd",
      "fghi",
      "jklmn",
      "jprst",
      "Hello",
      "bestprog"
    };
    SortSelection<string> objString = new SortSelection<string>(AS);
    objString.Print("Before sorting: objString");

    objString.Sort(true); // остортировать строки по возрастанию
    objString.Print("After sorting: objString");

    SortSelection<string> objString2 = new SortSelection<string>();
    objString2.Set(objString.Get());
    objString2.Print("objString2:");
  }
}

 

4. Текст всей программы (сокращенная версия)

После обработки всех предыдущих пунктов получается программа, сокращенный текст которой следующий.

// Разработка класса, который реализует алгоритм сортировки выбором
using System;
using static System.Console;

namespace ConsoleApp10
{
  // Обобщенный класс SortSelection<T> - реализует алгоритм сортировки выбором.
  // Чтобы сравнивать значения, нужно реализовать интерфейс IComparable<T>.
  class SortSelection<T> where T:IComparable<T>
  {
    // Одномерный массив с данными, которые будут сортироваться
    private T[] A;

    // Конструкторы.
    // Конструктор без параметров
    public SortSelection()
    {
      ...
    }

    // Конструктор, получающий внешний массив типа T[]
    public SortSelection(T[] A)
    {
      ...
    }

    // Конструктор, получающий входным экземпляр класса SortSelection<T>
    public SortSelection(SortSelection<T> obj)
    {
      ...
    }

    // Методы доступа.
    // Получить копию массива A
    public T[] Get()
    {
      ...
    }

    // Установить новое значение массива
    public void Set(T[] _A)
    {
      ...
    }

    // Методы сортировки
    // Метод, который сортирует весь массив.
    public void Sort(bool order)
    {
      ...
    }

    // Метод, реализующий алгоритм сортировки выбором в указанном диапазоне [pos1, pos2-1]
    public bool SortRange(bool order, int pos1, int pos2)
    {
      ...
    }

    // Вывод внутреннего массива на экран
    public void Print(string comment)
    {
      ...
    }
  }

  // Класс Program - тестирует работу класса SortSelection<T>
  class Program
  {
    static void Main(string[] args)
    {
      ...
    }
  }
}

 

5. Результат выполнения программы
objInt1 before sorting
3 5 -1 2 -4
objInt1 after sorting
-4 -1 2 3 5
objInt1.SortRange(false, 1, 3):
-4 2 -1 3 5
Before sorting: objString
abcd fghi jklmn jprst Hello bestprog
After sorting: objString
abcd bestprog fghi Hello jklmn jprst

 


Связанные темы