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




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


Зміст


Пошук на інших ресурсах:

1. Алгоритм сортування вибором. Особливості реалізації

Алгоритм сортування вибором використовується для одновимірного масиву. Сортування вибором дозволяє отримати відсортовану послідовність шляхом приєднання до неї одного елементу за іншим в правильному порядку.

На першому кроці алгоритму розглядаються усі елементи послідовності. Спочатку здійснюється пошук позиції елементу з мінімальним (максимальним) значенням. Елемент в знайденій позиції обмінюється з елементом на першій (нульовій) позиції.

На другому кроці розглядаються усі елементи послідовності крім першого, оскільки, перший елемент вже розміщено. Знову шукається елемент з мінімальним (максимальним) значенням, після чого цей елемент обмінюється з елементом на другій позиції.

Процес повторюється доки не буде сформовано нову послідовність. На кожному наступному кроці розглядається на один елемент менше.

Якщо елементи послідовності сортуються за зростанням, то на кожному кроці здійснюється пошук мінімального елементу. Якщо елементи послідовності сортуються за спаданням, то здійснюється пошук максимального елементу.

Якщо розглядається масив з n елементів, то кількість кроків алгоритму n-1. Швидкодія алгоритму – O(n2).

Переваги алгоритму:

  • простота реалізації;
  • реалізація алгоритму не потребує використання додаткового масиву.

Недоліки алгоритму:

  • низька швидкодія O(n2). Даний алгоритм підходить для сортування масивів невеликих розмірів.

Роботу алгоритму сортування вибором продемонстровано на рисунку 1. Розглядається масив з 7 цілих чисел. Алгоритм може бути застосований до будь-якої послідовності чисел.

Алгоритм сортування вибором. Приклад сортування масиву з 7 чисел

Рисунок 1. Алгоритм сортування вибором. Приклад сортування масиву з 7 чисел

 

2. Умова задачі

Розробити узагальнений клас, що містить засоби, що реалізують алгоритм сортування вибором. Продемонструвати роботу класу в функції main().

 

3. Розробка класу
3.1. Створення класу SortSelection. Початковий вигляд програми типу Console Application

Першим кроком розробки програми є створення шаблонного класу SortSelection.

#include <iostream>
using namespace std;

// Шаблонний клас, що реалізує алгоритм сортування вибором в одновимірному масиві
template <class T>
class SortSelection
{

}

void main(void)
{

}

 

3.2. Ввід внутрішніх змінних

На цьому етапі в клас вводяться приховані внутрішні змінні:

  • масив узагальненого типу T;
  • кількість елементів у масиві count.

Після введення змінних текст класу наступний:

...

// Шаблонний клас, що реалізує алгоритм сортування вибором в одновимірному масиві
template <class T>
class SortSelection
{
private:
  T* A; // внутрішній одновимірний масив
  int count; // кількість елементів у масиві
}

...

 

3.3. Внутрішній метод класу Copy(). Копіювання даних у внутрішній масив

Найбільш частою операцією в методах класу є копіювання даних зовнішнього масиву у внутрішній масив. Для реалізації цієї операції в розділ private класу вводиться внутрішній метод Copy(). Цей метод викликається з конструктора класу та з методу Set().

Текст методу наступний

// Внутрішній метод копіювання зовнішнього масиву у внутрішній масив A
void Copy(T* _A, int _count)
{
  // 1. Перевірити, чи коректне _count
  if (_count <= 0)
  {
    A = nullptr;
    count = 0;
    return;
  }

  try
  {
    // 2. Встановити нову кількість елементів
    count = _count;

    // 3. Виділити пам'ять для внутрішнього масиву A
    A = new T[count];
  }
  catch (bad_alloc e)
  {
    cout << e.what() << endl;
    return;
  }

  // 4. Скопіювати елементи A = _A
  for (int i = 0; i < count; i++)
    A[i] = _A[i];
}

 

3.4. Конструктори класу

Клас містить 3 конструктори, які розміщуються в розділі public:

  • конструктор без параметрів. Створює екземпляр класу з пустим (nullptr) масивом;
  • конструктор з двома параметрами. Заповнює внутрішній масив A даними зовнішнього масиву;
  • конструктор копіювання. Викликається при ініціалізації одного екземпляру іншим та при поверненні екземпляру класу з деякого методу операцією return. Про необхідність використання конструктора копіювання в подібних класах детально описується тут.

 

// Конструктори класу
// Конструктор без параметрів
SortSelection()
{
  A = nullptr;
  count = 0;
}

// Конструктор, що ініціалізує внутрішні дані зовнішнім масивом
SortSelection(T* _A, int _count)
{
  Copy(_A, _count); // скопіювати дані у внутрішній масив
}

// Конструктор копіювання - перенаправити на конструктор з 2 параметрами
SortSelection(const SortSelection& obj) :SortSelection(obj.A, obj.count)
{
}

 

3.5. Методи доступу до внутрішнього масиву Get(), Set()

У розділі public додано два методи (аксесори) для доступу до внутрішнього масиву A:

  • метод Get() – використовується, коли виникає необхідність отримати посилання (покажчик) на внутрішній масив A а також визначити кількість елементів цього масиву;
  • метод Set() – необхідний для заповнення масиву A новими даними.

 

// Методи доступу до внутрішнього масиву класу SortSelection
// Отримати кількість елементів масиву A та покажчик на масив A
T* Get(int* _count)
{
  *_count = count;
  return A;
}

// Встановити новий масив в екземплярі класу
void Set(T* _A, int _count)
{
  // Звільнити пам'ять, попередньо виділену під масив A
  if (count > 0)
  {
    delete[] A;
    count = 0;
  }

  // Скопіювати A = _A
  Copy(_A, _count);
}

 

3.6. Операторна функція operator=(). Перевантаження оператору присвоєння

Операторна функція operator=() викликається у випадках, якщо в програмі відбувається присвоєння одного екземпляру класу іншому екземпляру

objA = objB;

При цьому передбачається, що обидва екземпляри мають однаковий тип. Операторна функція operator=() розміщується в розділі public і має наступну реалізацію

// Операторна функція operator=() - необхідна для присвоювання масивів
SortSelection& operator=(SortSelection& obj)
{
  // Викликати метод Set() класу
  Set(obj.A, obj.count);

  // Повернути поточний екземпляр
  return *this;
}

 

3.7. Метод сортування даних Sort()

Основним методом класу є загальнодоступний (public) метод Sort(), який реалізує безпосереднє сортування даних в масиві. У методі реалізовано алгоритм сортування вставками. Метод отримує один параметр order, який визначає порядок сортування елементів. Якщо order=true, то сортування відбувається за зростанням елементів. Якщо order=false, то сортування відбувається за спаданням елементів.

Текст методу наступний

// Метод сортування Sort
// Метод отримує параметр order,
// - якщо order=true - сортування за зростанням,
// - якщо order=false - сортування за спаданням.
void Sort(bool order)
{
  int i, j, k;
  T x;

  for (i = 0; i < count; i++) // i - номер кроку
  {
    k = i;
    x = A[i];

    for (j = i + 1; j < count; j++)
      if (order)
      {
        if (A[j] < x) // пошук найменшого елементу
        {
          k = j; // k - позиція найменшого елементу в масиві A
          x = A[j];
        }
      }
    else
    {
      if (A[j] > x) // пошук найбільшого елементу
      {
        k = j; // k - позиція найбільшого елементу в масиві A
        x = A[j];
      }
    }

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

 

3.8. Метод Print(). Виведення масиву

Метод Print() використовується для виведення на екран даних в масиві A.

// Метод, що виводить внутрішній масив на екран
void Print(string comment)
{
  cout << comment << endl;
  for (int i = 0; i < count; i++)
    cout << A[i] << " ";
  cout << endl;
}

 

4. Тестування класу. Текст методу main()

У методі main() здійснюється тестування роботи методів класу SortSelection.

Текст функції наступний

void main(void)
{
  // Тестування класу SortSelection()
  // 1. Для масиву типу int
  // 1.1. Оголосити змінні
  int AI[] = { 2, 5, 1, 8, 3, 5, 4, 3, 7 };
  SortSelection<int> objInt(AI, 9);
  objInt.Print("objInt:");

  // Посортувати масив у порядку спадання
  objInt.Sort(false);
  objInt.Print("objInt after sorting:"); // вивести масив

  // 1.2. Тест конструктора копіювання
  SortSelection<int> objInt2 = objInt;
  objInt2.Print("objInt2:");

  // 1.3. Тест операторної функції operator=()
  SortSelection<int> objInt3;
  objInt3 = objInt;
  objInt3.Print("objInt3:");

  // 1.4. Тест методу Set()
  int AI2[] = { 0,5,2,3,3,4,5 };
  objInt2.Set(AI2, 7);
  objInt2.Print("objInt2:");

  // 1.5. Тест методу Get()
  int* AI3;
  int count3;
  AI3 = objInt3.Get(&count3);
  cout << "Array AI3:" << endl;
  for (int i = 0; i < count3; i++)
    cout << AI3[i] << " ";
  cout << endl;

  // 2. Тестування для масиву типу char
  char AC[] = { 'a', 'f', 'c', 'x', 'w', 'p' };
  SortSelection<char> objChar;
  objChar.Set(AC, 6); // метод Set()
  objChar.Print("objChar before sorting:");

  // посортувати масив objChar
  objChar.Sort(false);
  objChar.Print("objChar after sorting:");
}

 

5. Загальна структура програми. Скорочений варіант

Опрацювавши попередні кроки можна отримати повноцінний клас SortSelection, що реалізує алгоритм сортування вставками. Текст усієї програми, що містить клас SortSelection та функцію main() в скороченому вигляді представлений нижче

#include <iostream>
using namespace std;

// Шаблонний клас, що реалізує алгоритм сортування вибором в одновимірному масиві
template <class T>
class SortSelection
{
private:
  T* A; // внутрішній одновимірний масив
  int count; // кількість елементів у масиві

  // Внутрішній метод копіювання зовнішнього масиву у внутрішній масив A
  void Copy(T* _A, int _count)
  {
    ...
  }

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

  // Конструктор, що ініціалізує внутрішні дані зовнішнім масивом
  SortSelection(T* _A, int _count)
  {
    ...
  }

  // Конструктор копіювання
  SortSelection(const SortSelection& obj) :SortSelection(obj.A, obj.count)
  {
  }

  // Методи доступу до внутрішнього масиву класу SortSelection
  // Отримати кількість елементів масиву A та покажчик на масив A
  T* Get(int* _count)
  {
    ...
  }

  // Встановити новий масив в екземплярі класу
  void Set(T* _A, int _count)
  {
    ...
  }

  // Деструктор
  ~SortSelection()
  {
    ...
  }

  // Операторна функція operator=()
  SortSelection& operator=(SortSelection& obj)
  {
    ...
  }

  // Метод сортування Sort()
  void Sort(bool order)
  {
    ...
  }

  // Метод, що виводить внутрішній масив на екран
  void Print(string comment)
  {
    ...
  }
};

void main(void)
{
  ...
}

 

6. Результат виконання програми

Після запуску на виконання програма видасть наступний результат

objInt:
2 5 1 8 3 5 4 3 7
objInt after sorting:
8 7 5 5 4 3 3 2 1
objInt2:
8 7 5 5 4 3 3 2 1
objInt3:
8 7 5 5 4 3 3 2 1
objInt2:
0 5 2 3 3 4 5
Array AI3:
8 7 5 5 4 3 3 2 1
objChar before sorting:
a f c x w p
objChar after sorting:
x w p f c a

 


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