C++. Разработка класса реализующего алгоритм сортировки выбором
Содержание
- 1. Алгоритм сортировки выбором. Особенности реализации
- 2. Условие задачи
- 3. Разработка класса
- 3.1. Создание класса SortSelection. Начальный вид программы типа Console Application
- 3.2. Ввод внутренних переменных
- 3.3. Внутренний метод класса Copy(). Копирование данных во внутренний массив
- 3.4. Конструкторы класса
- 3.5. Методы доступа к внутреннему массиву Get(), Set()
- 3.6. Операторная функция operator=(). Перегрузка оператора присваивания
- 3.7. Метод сортировки данных Sort()
- 3.8. Метод Print(). Вывод массива
- 4. Тестирование класса. Текст метода main()
- 5. Общая структура программы. Сокращенный вариант
- 6. Результат выполнения программы
- Связанные темы
Поиск на других ресурсах:
1. Алгоритм сортировки выбором. Особенности реализации
Алгоритм сортировки выбором используется для одномерного массива. Сортировка выбором позволяет получить отсортированную последовательность путем присоединения к ней одного элемента за другим в нужном порядке.
На первом шаге алгоритма рассматриваются все элементы последовательности. Сначала осуществляется поиск позиции элемента с минимальным (максимальным) значением. Элемент в найденной позиции обменивается с элементом на первой (нулевой) позиции.
На втором шаге рассматриваются все элементы последовательности кроме первого, поскольку, первый элемент уже размещен. Снова ищется элемент с минимальным (максимальным) значением, после чего этот элемент обменивается с элементом на второй позиции.
Процесс повторяется пока не будет сформирована новая последовательность. На каждом следующем шаге рассматривается на один элемент меньше.
Если элементы последовательности сортируются по возрастанию, то на каждом шаге осуществляется поиск минимального элемента. Если элементы последовательности сортируются по убыванию, то осуществляется поиск максимального элемента.
Если рассматривается массив из n элементов, то количество шагов алгоритма n-1. Быстродействие алгоритма – O(n2).
Преимущества алгоритма:
- простота реализации;
- реализация алгоритма не требует использования дополнительного массива.
Недостатки алгоритма:
- низкое быстродействие. Данный алгоритм подходит для сортировки массивов небольших размеров.
Работа алгоритма сортировки выбором продемонстрирована на рисунке 1. Рассматривается массив из 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
⇑
Связанные темы
- Разработка класса, реализующего массив строк типа char*
- Разработка класса Random генерирования случайных чисел
- Разработка класса, реализующего линейный поиск в одномерном массиве
⇑