Розробка узагальненого класу, що реалізує алгоритм сортування вибором на мові 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

⇑

Зв’язані теми

⇑

BestProg

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