лаба 2
.pdfФедеральное агентство связи ордена Трудового Красного Знамени Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Московский Технический Университет связи и информатики
Кафедра «Математической кибернетики и информационных технологий»
Лабораторная работа №2 Методы сортировки
Выполнила студентка группы БСТ1904 Пантелеева К.А.
Вариант №15
|
|
Оглавление |
|
1 |
Задание ...................................................................................................................... |
3 |
|
2 |
Ход лабораторной работы ....................................................................................... |
3 |
|
|
2.1 |
Метод сортировки обменом.............................................................................. |
3 |
|
2.2 |
Код программы................................................................................................... |
3 |
|
2.3 |
Тестирование ...................................................................................................... |
6 |
3 |
Вывод......................................................................................................................... |
7 |
|
Список использованных источников ........................................................................ |
7 |
2
1 Задание
1) Реализовать метод сортировки обменом строк числовой матрицы.
2) Добавить реализацию быстрой сортировки (quicksort).
3) Оценить время работы каждого алгоритма сортировки и сравнить его со временем работы стандартной функции сортировки, используемой в выбранном языке программирования.
2 Ход лабораторной работы
2.1Метод сортировки обменом
1)Программа получает на вход массив
2)Элементы массива располагается сверху вниз, от нулевого элемента – к последнему
3)Шаг сортировки состоит в проходе снизу вниз по массиву
4)По пути просматриваются пары соседних элементов
5)Если какой-то элемент пары находится в неправильном порядке, то они меняются местами
2.2Код программы
#pragma once #include <ctime> #include <algorithm> <…>
#pragma endregion
int Number(int i, TextBox^ TB, int& len)
{
int Num = 0; wchar_t c; len = 0;
do
{
c = TB->Text[i]; switch (c)
{
case '1':
Num = Num * 10 + 1; break;
case '2':
Num = Num * 10 + 2; break;
case '3':
Num = Num * 10 + 3; break;
case '4':
Num = Num * 10 + 4; break;
case '5':
Num = Num * 10 + 5; break;
case '6':
Num = Num * 10 + 6; break;
case '7':
Num = Num * 10 + 7; break;
case '8':
3
Num = Num * 10 + 8; break;
case '9':
Num = Num * 10 + 9; break;
case '0':
Num = Num * 10 + 0; break;
}
if (i >= TB->Text->Length - 1) break;
else
{
i++; len++;
}
}while (TB->Text[i] == '1' || TB->Text[i] == '2' || TB->Text[i] == '3'
||TB->Text[i] == '4' || TB->Text[i] == '5' || TB->Text[i] == '6'
||TB->Text[i] == '7' || TB->Text[i] == '8' || TB->Text[i] == '9'
||TB->Text[i] == '0');
return Num;
}
void art(int* arr, int N, int len, TextBox^ TB)
{
int c = 0;
for (int i = 0; i < N; i++)
{
if (TB->Text[i] == '1' || TB->Text[i] == '2' || TB->Text[i] ==
'3'
|| TB->Text[i] == '4' || TB->Text[i] == '5' || TB->Text[i]
== '6'
|| TB->Text[i] == '7' || TB->Text[i] == '8' || TB->Text[i]
== '9' || TB->Text[i] == '0')
{
}
}
arr[c] = Number(i, TB, len); c++;
i += len;
}
void work(int& num, int N, TextBox^ TB)
{
for (int i = 0; i < N; i++)
{
if (TB->Text[i] == ' ') num++;
}
if (TB->Text[N - 1] != ' ') num++;
}
void sortobmen(int* arr, int N)
{
int c;
for (int i = 0; i < N - 1; i++)
{
for (int j = 0; j < N - 1; j++)
{
if (arr[j + 1] < arr[j])
{
c = arr[j + 1]; arr[j + 1] = arr[j];
4
arr[j] = c;
}
}
}
}
void sortquick(int* arr, int left, int right)
{
int pivot;
int l_hold = left; int r_hold = right; pivot = arr[left]; while (left < right)
{
while ((arr[right] >= pivot) && (left < right)) right--;
if (left != right)
{
arr[left] = arr[right]; left++;
}
while ((arr[left] <= pivot) && (left < right)) left++;
if (left != right)
{
arr[right] = arr[left]; right--;
}
}
arr[left] = pivot; pivot = left;
left = l_hold; right = r_hold; if (left < pivot)
sortquick(arr, left, pivot - 1); if (right > pivot)
sortquick(arr, pivot + 1, right);
}
private: System::Void button1_Click(System::Object^ sender, System::EventArgs^ e) { textBox2->Text = "";
int N = textBox1->Text->Length, count = 0, len; work(count, N, textBox1);
int* arr = new int[count]; art(arr, N, len, textBox1); clock_t t = clock(); sortobmen(arr, count);
t = clock() - t;
label1->Text = "Время работы программы: " + t + " тактов"; for (int i = 0; i < count; i++)
{
textBox2->Text += arr[i] + " ";
}
}
private: System::Void button2_Click(System::Object^ sender, System::EventArgs^ e) { textBox2->Text = "";
int N = textBox1->Text->Length, count = 0, len; work(count, N, textBox1);
int* arr = new int[count]; art(arr, N, len, textBox1); clock_t t = clock(); sortquick(arr, 0, count - 1); t = clock() - t;
label1->Text = "Время работы программы: " + t + " тактов"; for (int i = 0; i < count; i++)
5
{
textBox2->Text += arr[i] + " ";
}
}
private: System::Void button3_Click(System::Object^ sender, System::EventArgs^ e) { textBox2->Text = "";
int N = textBox1->Text->Length, count = 0, len; work(count, N, textBox1);
int* arr = new int[count]; art(arr, N, len, textBox1); clock_t t = clock(); std::sort(arr, arr + count); t = clock() - t;
label1->Text = "Время работы программы: " + t + " тактов"; for (int i = 0; i < count; i++)
{
textBox2->Text += arr[i] + " ";
}
}
};
}
2.3 Тестирование
Введем «2567176 37356 6732 7872678 7821 2673 267 26 78 762 8761 92 1 298 90»
и посмотрим, как отсортирует программа. На рисунке 1 приведены результаты стандартной сортировки данной последовательности.
Рисунок 1 – Результаты стандартной сортировки
Теперь отсортируем данную цепочку чисел через быструю сортировку (рисунок
2).
Рисунок 2 – Результаты быстрой сортировки
А теперь отсортируем данную цепочку сортировкой обмена (рисунок 3).
6
Рисунок 3 – Результаты сортировки обменом
3 Вывод
В результате данной работы я научилась разрабатывать алгоритм сортировки в С++. Также мы можем сделать вывод, сравнив время работы каждой сортировки, что быстрая сортировка имеет наименьшее время работы, тогда как у стандартной сортировки и сортировки обменов время работы одинаковое.
Список использованных источников
1)ГОСТ 7.1-2001 СИБИД. Библиографическая запись. Библиографическое описание. Общие требования и правила составления [электронный ресурс]
URL: https://internet-law.ru/gosts/gost/1560 (дата обращения 28.03.2020)
2)ГОСТ 7.32-2001 СИБИД. Отчет о научно-исследовательской работе. Структура и правила оформления (с Изменением N 1) [электронный ресурс]
URL: http://docs.cntd.ru/document/gost-7-32-2001-sibid (дата обращения 28.03.2020)
7