Статья опубликована в рамках: Научного журнала «Студенческий» № 30(242)
Рубрика журнала: Информационные технологии
Скачать книгу(-и): скачать журнал часть 1, скачать журнал часть 2, скачать журнал часть 3, скачать журнал часть 4
РЕАЛИЗАЦИЯ СОРТИРОВКИ СЛИЯНИЕМ ДЛЯ ОБЪЕКТА ТИПА “ВЕКТОР”
IMPLEMENTATION OF MERGE SORT FOR AN OBJECT OF “VECTOR” TYPE
Anton Gavrunov
student, Institute of Engineering and Digital Technologies, Belgorod State National Research University,
Russia, Belgorod
АННОТАЦИЯ
Целью данной работы является, программная реализация сортировки слиянием для объекта типа “вектор”. Для достижения успешного результата, предстоит выполнить следующие задачи. Реализовать программу на языке C++. Протестировать реализованную программу. Оценить временную сложность сортировки слиянием.
ABSTRACT
The goal of this work is a software implementation of merge sort for an object of the “vector” type. To achieve a successful result, the following tasks must be completed. Implement the program in C++. Test the implemented program. Estimate the time complexity of merge sort.
Ключевые слова: функция, алгоритм, вектор, метод, сортировка, массив, временная сложность.
Keywords: function, algorithm, vector, method, sorting, array, time complexity.
Перед реализацией алгоритма сортировки была создана блок схема работы программы, диаграмма показана на рисунке 1.
Рисунок 1. Блок-схема алгоритма сортировка
Для реализации сортировки слиянием для объекта типа “вектор” был разработан класс. Также абстрактный тип данных, который предоставляет для работы с элементами этого типа определенный набор функций, а также возможность создавать элементы этого типа при помощи специальных функций. Вся внутренняя структура такого типа скрыта от разработчика программного обеспечения – в этом заключается суть абстракции.
В ходе реализации был создан класс “Vector”, который послужит описанием математического объекта вектор. В области действия модификатора доступа private были объявлены 2 переменные X, Y для хранения координат вектора. Также была объявлена переменная length, которая отвечает за длину вектора.
Модификаторы доступа — это ключевые слова, которые задают объявленный уровень доступности члена или типа.
private: Доступ ограничен содержащим типом.
public: Неограниченный доступ.
protected: Доступ ограничен содержащим классом или типами, которые являются производными от содержащего класса.
|
Листинг 1. Модификатор доступа private |
|
private: double x0, y0, x, y, length; |
Далее в области действия модификатора доступа public были созданы следующие методы: SetX( ), SetY( ), SetX0( ), SetY0( ), setCoord(). Данные методы позволяют установить значения переменных X, Y, X0, Y0, как в паре, так и по отдельности.
|
Листинг 2. |
|
public: Vector(); void setX(double x) { this->x = x; countLength(); } void setY(double y) { this->y = y; countLength(); } void setX0(double x0) { this->x0 = x0; countLength(); } void setY0(double y0) { this->y0 = y0; countLength(); } void setCoord(double x, double y, double x0 = 0, double y0 = 0) { this->x = x; this->y = y; this->x0 = x0; this->y0 = y0; countLength(); } |
В каждом из этих методов вызывается метод countLength(), предназначенный для длины вектора.
|
Листинг 3. |
|
void countLength() {this->length = sqrt(pow(this->x - x0, 2) + pow(this->y - y0, 2));} |
Раcсчет длинны вектора выполняется по формуле из векторной алгебры:
ǀāǀ= 
(1)
И последний метод класса “Vector” – метод для вывода координат в консоль.
|
Листинг 4. |
|
void outVector() {if (x0 != 0 && y0 != 0) {cout << "X0: " << x0 << " Y0: " << y0 << " X:" << x << " Y:" << y << " Длина: " << length << endl;} else { cout << "X: " << x << " Y: " << y << " Длина: " << length << endl;}} |
Также были перегружены операторы (>, <, >=, <=, ==, !=, =), это было сделано для удобства сравнения длин векторов в сортировке.
|
Листинг 5. |
|
bool operator > (Vector v) {counter++; return (this->length > v.length);} bool operator < (Vector v) {counter++; return (this->length < v.length);} bool operator >= (Vector v) {counter++; return (this->length >= v.length);} bool operator <= (Vector v) {counter++; return (this->length <= v.length);} bool operator == (Vector v) {counter++; return (this->length == v.length);} bool operator != (Vector v) {counter++; return (this->length != v.length);} void operator = (Vector v) { counter++; this->length = v.length; this->x = v.x; this->y = v.y; this->x0 = v.x0; this->y0 = v.y0; } |
Далее реализуем алгоритм сортировки слиянием, помещаем его в функцию sort.
|
Листинг 6. |
|
void sort(int l, int r) { if (r == l) return; if (r - l == 1) { if (a[r] < a[l]) swap(a[r], a[l]); return; } int m = (r + l) / 2; sort(l, m); sort(m + 1, r); Vector buf[SIZE]; int xl = l; int xr = m + 1; int cur = 0; while (r - l + 1 != cur) { if (xl > m) buf[cur++] = a[xr++]; else if (xr > r) buf[cur++] = a[xl++]; else if (a[xl] > a[xr]) buf[cur++] = a[xr++]; else buf[cur++] = a[xl++]; } for (int i = 0; i < cur; i++) a[i + l] = buf[i];} |
Далее, в функции main прописывается функция setlocale(LC_ALL, "Rus"), для отображения кириллицы, функция srand(time(NULL)), нужная для генерации случайных чисел. Затем мы вызываем все выше описанные функции и выводим количество операций над элементами.
Протестируем работу программы на массиве состоящем из 5 элементов. Результат работы можно увидеть на рисунке 2.
Рисунок 2. Работа программы для массива из 5 элементов
Таблица 1.
Тестовые данные.
|
Количество элементов |
5 |
10 |
20 |
40 |
|
Количество операций над элементами |
28 |
77 |
213 |
550 |
На основе заполненной таблицы построен график зависимости количества операций над элементами от количества элементов в массиве (Рисунок 3).
Рисунок 3. График зависимости количества операций от количества элементов в массиве
Список литературы:
- Никлаус Вирт. Алгоритмы и структуры данных. Новая версия для Оберона / Пер. с англ. Ткачев Ф. В. – Москва: ДМК Пресс, 2010. – 272 с.
- Д.Кнут. Искусство программирования для ЭВМ. Сортировка и поиск / Д.Кнут. – Москва: Мир, 1978. – 355 с.
- Роберт Седжвик. Часть III. Глава 6. Элементарные методы сортировки: 6.2 Сортировка выбором // Алгоритмы на С++ = Algorithms in C++. — М.: «Вильямс», 2011. — С. 246-247.
- Бьерн Страуструп Язык программирования C++. изд. Addison-Wesley, 1985.
Оставить комментарий