Лабораторная работа: 10.
Тема: Алгоритмы сортировки и оценка их сложности.
Файл: Lab10_YaP_2019_1S.pdf
Обратите внимание:
В файлах Source.cpp, Source.cs и *.pas помимо прочего, так же имеются примечания к программам с различными комментариями и пояснениями.
При оформлении программ в сети Интернет я их удаляю, чтобы не нагромождать эти программы и тем самым не затруднять их восприятие.
Язык: C++.
Среда: Microsoft Visual Studio 2019 v16.3.0.
Платформа: x64.
Задание:
Напишите программу, которая выполняет следующие функции:
1. Генерацию элементов массива с заданной размерностью;
2. Сортировку массива каждым из 6 способов (пузырьковая сортировка, сортировка вставкой, сортировка выбором, быстрая сортировка, сортировка слиянием, шейкерная сортировка);
3. Осуществляет подсчет времени сортировки и количества перестановок.
Примечание:
1. Алгоритмы сортировок скопировал из открытых источников сети Интернет (веб-адреса не помню). Копировал первые встретившиеся, при том что разновидностей каждого из них были десятки. Поэтому представленные здесь варианты, вероятнее всего, являются не самыми оптимальными.
2. Наименьшую разрядность массива указал 1000 элементов (меньше нет смысла: секундомер всегда будет равен нулю).
3. В блок-схему программы я не включил схемы самих сортировок, поскольку их рисование заняло бы огромное количество времени (хорошо защитил и без них).
4. Блок-схема составлена с помощью веб-сайта Draw.io.
5. Источником Таблицы № 2 и Рисунка № 1 является статья: Знай сложности алгоритмов (2013).
6. Отчет создан в программе: Microsoft Office 2013 Professional Plus v15.0.5101.1001.
7. Во вложении находится скриншот иллюстрирующий работу программы.
ЛР № 10, задание № 5
1/11. Source.cpp:
C++ | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| /*
*Лабораторная работа: 10.
*Тема: Алгоритмы сортировки и оценка их сложности.
*Пункт: отсутствует.
*Файл: Lab10_YaP_2019_1S.pdf
*
*Язык: C++.
*Среда: Microsoft Visual Studio 2019 v16.3.0.
*Платформа: x64.
*Изменение: 03.01.2020.
*
*Вариант: отсутствует.
*Защита: 27.12.2019.
*Задание: БН. Напишите программу, которая выполняет следующие функции:
*1. Генерацию элементов массива с заданной размерностью;
*2. Сортировку массива каждым из 6 способов (пузырьковая сортировка, сортировка вставкой, сортировка выбором, быстрая сортировка,
* сортировка слиянием, шейкерная сортировка);
*3. Осуществляет подсчет времени сортировки и количества перестановок.
*/
#include <iostream> // Требуется для SETLOCATE, PRINTF, CIN. //
#include "Header.h"
void main () {
setlocale (LC_ALL, "Russian");
int Choice = 0, CounterVariable = 0, DimensionVariable = 0;
float StopwatchVariable = 0;
int &CounterLink = CounterVariable;
int *Counter = &CounterLink;
int &Dimension = DimensionVariable;
float &StopwatchLink = StopwatchVariable;
float *Stopwatch = &StopwatchLink;
void (*PointerSortFunction []) (int*, int, float*, int*) = {PuzirekSortFunction, VstavkaSortFunction, ViborSortFunction,
BistrayaSortFunction, SliyanieSortFunction, SheikernayaSortFunction};
void (*PointerArrayFunction []) (int*, int) = {InicializastionArrayFunction, WriteArrayFunction};
printf ("1. Введите размерность массива (от 1000 до +oo): ");
cin >> Dimension;
if (Dimension < 1000) {
MessageFunction ();
}
int *SourceArray = new int [Dimension]; // Объявление SOURCEARRAY. //
(*PointerArrayFunction [0]) (SourceArray, Dimension);
(*PointerArrayFunction [1]) (SourceArray, Dimension);
printf ("\n2. Каким способом вы хотите упорядочить массив?\n\n1) Сортировка Пузырком........1\n2) Сортировка Вставкой........2\n3) С"
"ортировка Выбором.........3\n4) Быстрая сортировка.........4\n5) Сортировка Слиянием........5\n6) Шейкерная сортировка.......6"
"\n\nВаш выбор: ");
cin >> Choice;
if ((Choice < 1) || (Choice > 6)) {
MessageFunction ();
}
(*PointerSortFunction [Choice - 1]) (SourceArray, Dimension, Stopwatch, Counter);
(*PointerArrayFunction [1]) (SourceArray, Dimension);
printf ("\n3. Время выполнения алгоритма сортировки: %.3f секунд(-ы).\n\n4. Количество перестановок: %d шт.\n\n", StopwatchLink,
CounterLink);
delete [] SourceArray; // Деструктор SOURCEARRAY. //
ExitProgramFunction ();
} |
|
2/11. Header.h:
C++ | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| /*
*Лабораторная работа: 10.
*Тема: Алгоритмы сортировки и оценка их сложности.
*Пункт: 5. Задание.
*Файл: Lab10_YaP_2019_1S.pdf
*
*Язык: C++.
*Среда: Microsoft Visual Studio 2019 v16.3.0.
*Платформа: x64.
*Изменение: 03.01.2020.
*
*Вариант: отсутствует.
*Защита: 27.12.2019.
*Задание: БН. (...)
*/
using namespace std;
void ExitProgramFunction (); // Объявление EXITPROGRAMFUNCTION. //
void WriteArrayFunction (int *SourceArray, int Dimension); // Объявление WRITEARRAYFUNCTION. //
void SheikernayaSortFunction (int *SourceArray, int Dimension, float *Stopwatch, int *Counter); // Объявл. SHEIKERNAYASORTFUNCTION. //
void SliyanieSortFunction (int *SourceArray, int Dimension, float *Stopwatch, int *Counter); // Объявление SLIYANIESORTFUNCTION. //
void BistrayaSortFunction (int *SourceArray, int Dimension, float *Stopwatch, int *Counter); // Объявление BISTRAYASORTFUNCTION. //
void ViborSortFunction (int *SourceArray, int Dimension, float *Stopwatch, int *Counter); // Объявление VIBORSORTFUNCTION. //
void VstavkaSortFunction (int *SourceArray, int Dimension, float *Stopwatch, int *Counter); // Объявление VSTAVKASORTFUNCTION. //
void PuzirekSortFunction (int *SourceArray, int Dimension, float *Stopwatch, int *Counter); // Объявление PUZIREKSORTFUNCTION. //
void InicializastionArrayFunction (int *SourceArray, int Dimension); // О. INICIALIZATIONARRAYFUNCTION. //
void MessageFunction (); // Объявление MESSAGEFUNCTION. // |
|
3/11. InicializastionArrayFunction.cpp:
C++ | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| /*
*Лабораторная работа: 10.
*Тема: Алгоритмы сортировки и оценка их сложности.
*Пункт: 5. Задание.
*Файл: Lab10_YaP_2019_1S.pdf
*
*Язык: C++.
*Среда: Microsoft Visual Studio 2019 v16.3.0.
*Платформа: x64.
*Изменение: 04.01.2020.
*
*Вариант: отсутствует.
*Защита: 27.12.2019.
*Задание: БН. (...)
*/
#include <iostream> // Требуется для SRAND, RAND. //
#include <ctime> // Требуется для TIME. //
#include "Header.h"
void InicializastionArrayFunction (int *SourceArray, int Dimension) { // Определение INICIALIZATIONARRAYFUNCTION. //
srand (time (0)); // TIME (0) - инициализация локального времени системы. //
for (int i = 0; i < Dimension; i++) {
*(SourceArray + i) = rand () % 1999 - 999; // SOURCEARRAY E [-999..999]. //
}
} |
|
4/11. PuzirekSortFunction.cpp:
C++ | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| /*
*Лабораторная работа: 10.
*Тема: Алгоритмы сортировки и оценка их сложности.
*Пункт: 5. Задание.
*Файл: Lab10_YaP_2019_1S.pdf
*
*Язык: C++.
*Среда: Microsoft Visual Studio 2019 v16.3.0.
*Платформа: x64.
*Изменение: 04.01.2020.
*
*Вариант: отсутствует.
*Защита: 27.12.2019.
*Задание: БН. (...)
*/
#include <iostream> // Требуется для PRINTF. //
#include <ctime> // Требуется для CLOCK. //
#include "Header.h"
void PuzirekSortFunction (int *SourceArray, int Dimension, float *Stopwatch, int *Counter) { // Определение PUZIREKSORTFUNCTION. //
int Temporary = 0;
*Stopwatch = clock (); // Включение STOPWATCH. //
for (int i = 0; i < Dimension - 1; i++) {
for (int j = i + 1; j < Dimension; j++) {
if (*(SourceArray + j) < *(SourceArray + i)) {
Temporary = *(SourceArray + i);
*(SourceArray + i) = *(SourceArray + j);
*(SourceArray + j) = Temporary;
*Counter += 1; // Вычисление количества перестановок. //
}
}
}
*Stopwatch = (clock () - *Stopwatch) / CLOCKS_PER_SEC; // Выключение STOPWATCH. //
} |
|
5/11. VstavkaSortFunction.cpp:
C++ | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| /*
*Лабораторная работа: 10.
*Тема: Алгоритмы сортировки и оценка их сложности.
*Пункт: 5. Задание.
*Файл: Lab10_YaP_2019_1S.pdf
*
*Язык: C++.
*Среда: Microsoft Visual Studio 2019 v16.3.0.
*Платформа: x64.
*Изменение: 04.01.2020.
*
*Вариант: отсутствует.
*Защита: 27.12.2019.
*Задание: БН. (...)
*/
#include <iostream> // Требуется для PRINTF. //
#include <ctime> // Требуется для CLOCK. //
#include "Header.h"
void VstavkaSortFunction (int *SourceArray, int Dimension, float *Stopwatch, int *Counter) { // Определение VSTAVKASORTFUNCTION. //
int Temporary = 0;
*Stopwatch = clock (); // Включение STOPWATCH. //
for (int i = 1; i < Dimension; i++) {
for (int j = i; (j > 0) && (*(SourceArray + j) < *(SourceArray + j - 1)); j--) {
Temporary = *(SourceArray + j - 1);
*(SourceArray + j - 1) = *(SourceArray + j);
*(SourceArray + j) = Temporary;
*Counter += 1; // Вычисление количества перестановок. //
}
}
*Stopwatch = (clock () - *Stopwatch) / CLOCKS_PER_SEC; // Выключение STOPWATCH. //
} |
|
6/11. ViborSortFunction.cpp:
C++ | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| /*
*Лабораторная работа: 10.
*Тема: Алгоритмы сортировки и оценка их сложности.
*Пункт: 5. Задание.
*Файл: Lab10_YaP_2019_1S.pdf
*
*Язык: C++.
*Среда: Microsoft Visual Studio 2019 v16.3.0.
*Платформа: x64.
*Изменение: 04.01.2020.
*
*Вариант: отсутствует.
*Защита: 27.12.2019.
*Задание: БН. (...)
*/
#include <iostream> // Требуется для PRINTF. //
#include <ctime> // Требуется для CLOCK. //
#include "Header.h"
void ViborSortFunction (int *SourceArray, int Dimension, float *Stopwatch, int *Counter) { // Определение VIBORSORTFUNCTION. //
int MinElement = 0, Temporary = 0;
*Stopwatch = clock (); // Включение STOPWATCH. //
for (int i = 0; i < Dimension - 1; i++) {
MinElement = i;
for (int j = i + 1; j < Dimension; j++) {
if (*(SourceArray + j) < *(SourceArray + MinElement)) {
MinElement = j;
}
}
if (i != MinElement) {
Temporary = *(SourceArray + i);
*(SourceArray + i) = *(SourceArray + MinElement);
*(SourceArray + MinElement) = Temporary;
*Counter += 1; // Вычисление количества перестановок. //
}
}
*Stopwatch = (clock () - *Stopwatch) / CLOCKS_PER_SEC; // Выключение STOPWATCH. //
} |
|
7/11. BistrayaSortFunction.cpp:
C++ | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| /*
*Лабораторная работа: 10.
*Тема: Алгоритмы сортировки и оценка их сложности.
*Пункт: 5. Задание.
*Файл: Lab10_YaP_2019_1S.pdf
*
*Язык: C++.
*Среда: Microsoft Visual Studio 2019 v16.3.0.
*Платформа: x64.
*Изменение: 04.01.2020.
*
*Вариант: отсутствует.
*Защита: 27.12.2019.
*Задание: БН. (...)
*/
#include <iostream> // Требуется для PRINTF. //
#include <ctime> // Требуется для CLOCK. //
#include "Header.h"
void QuickSort (int *SourceArray, int LeftIndex, int RightIndex, int *Counter) { // Объявление и определение
int i = LeftIndex, j = RightIndex, Temporary = 0; // QUICKSORT. //
int MiddleElement = *(SourceArray + ((LeftIndex + RightIndex) / 2));
do {
while (*(SourceArray + i) < MiddleElement) {
i++;
}
while (*(SourceArray + j) > MiddleElement) {
j--;
}
if (i <= j) {
if (i < j) {
Temporary = *(SourceArray + i);
*(SourceArray + i) = *(SourceArray + j);
*(SourceArray + j) = Temporary;
*Counter += 1; // Вычисление количества
} // перестановок. //
i++;
j--;
}
} while (i <= j);
if (i < RightIndex) {
QuickSort (SourceArray, i, RightIndex, Counter);
}
if (j > LeftIndex) {
QuickSort (SourceArray, LeftIndex, j, Counter);
}
}
void BistrayaSortFunction (int *SourceArray, int Dimension, float *Stopwatch, int *Counter) { // Определение BISTRAYASORTFUNCTION. //
int LeftIndex = 0, RightIndex = Dimension - 1;
*Stopwatch = clock (); // Включение STOPWATCH. //
QuickSort (SourceArray, LeftIndex, RightIndex, Counter);
*Stopwatch = (clock () - *Stopwatch) / CLOCKS_PER_SEC; // Выключение STOPWATCH. //
} |
|
8/11. SliyanieSortFunction.cpp:
C++ | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| /*
*Лабораторная работа: 10.
*Тема: Алгоритмы сортировки и оценка их сложности.
*Пункт: 5. Задание.
*Файл: Lab10_YaP_2019_1S.pdf
*
*Язык: C++.
*Среда: Microsoft Visual Studio 2019 v16.3.0.
*Платформа: x64.
*Изменение: 04.01.2020.
*
*Вариант: отсутствует.
*Защита: 27.12.2019.
*Задание: БН. (...)
*/
#include <iostream> // Требуется для PRINTF. //
#include <ctime> // Требуется для CLOCK. //
#include "Header.h"
void MergeSort (int *SourceArray, int Length, int *LeftArray, int LengthLeftArray, int *RightArray, int LengthRightArray, int *Counter) {
int i = 0, j = 0; // Объявление и определение
while ((i < LengthLeftArray) || (j < LengthRightArray)) { // MERGESORT. //
if ((i < LengthLeftArray) & (j < LengthRightArray)) {
if(*(LeftArray + i) <= *(RightArray + j)) {
*(SourceArray + i + j) = *(LeftArray + i);
i++;
*Counter += 1; // Вычисление количества
} // перестановок. //
else {
*(SourceArray + i + j) = *(RightArray + j);
j++;
*Counter += 1; // Вычисление количества
} // перестановок. //
}
else {
if(i < LengthLeftArray) {
*(SourceArray + i + j) = *(LeftArray + i);
i++;
*Counter += 1; // Вычисление количества
} // перестановок. //
else {
if (j < LengthRightArray) {
*(SourceArray + i + j) = *(RightArray + j);
j++;
*Counter += 1; // Вычисление количества
} // перестановок. //
}
}
}
}
void DeleteSort (int *SourceArray, int Dimension, int *Counter) { // Объявление и определение
if (Dimension > 1) { // DELETESORT. //
int MiddleElement = Dimension / 2;
int RightElement = Dimension - MiddleElement;
int *LeftArray = new int [MiddleElement];
int *RightArray = new int [RightElement];
for (int i = 0; i < Dimension; i++) {
if (i < MiddleElement) {
*(LeftArray + i) = *(SourceArray + i);
}
else {
*(RightArray + i - MiddleElement) = *(SourceArray + i);
}
}
DeleteSort (LeftArray, MiddleElement, Counter);
DeleteSort (RightArray, RightElement, Counter);
MergeSort (SourceArray, Dimension, LeftArray, MiddleElement, RightArray, RightElement, Counter);
delete [] LeftArray; // Деструктор LEFTARRAY. //
delete [] RightArray; // Деструктор RIGHTARRAY. //
}
}
void SliyanieSortFunction (int *SourceArray, int Dimension, float *Stopwatch, int *Counter) { // Определение SLIYANIESORTFUNCTION. //
*Stopwatch = clock (); // Включение STOPWATCH. //
DeleteSort (SourceArray, Dimension, Counter);
*Stopwatch = (clock () - *Stopwatch) / CLOCKS_PER_SEC; // Выключение STOPWATCH. //
} |
|
9/11. SheikernayaSortFunction.cpp:
C++ | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| /*
*Лабораторная работа: 10.
*Тема: Алгоритмы сортировки и оценка их сложности.
*Пункт: 5. Задание.
*Файл: Lab10_YaP_2019_1S.pdf
*
*Язык: C++.
*Среда: Microsoft Visual Studio 2019 v16.3.0.
*Платформа: x64.
*Изменение: 04.01.2020.
*
*Вариант: отсутствует.
*Защита: 27.12.2019.
*Задание: БН. (...)
*/
#include <iostream> // Требуется для PRINTF. //
#include <ctime> // Требуется для CLOCK. //
#include "Header.h"
void SheikernayaSortFunction (int *SourceArray, int Dimension, float *Stopwatch, int *Counter) { // Определение
int i = 0, MinIndex = 0, MaxIndex = Dimension - 1, Temporary = 0; // SHEIKERNAYASORTFUNCTION. //
*Stopwatch = clock (); // Включение STOPWATCH. //
while (MinIndex <= MaxIndex) {
for (i = MaxIndex; i >= MinIndex; i--) {
if (*(SourceArray + i - 1) > *(SourceArray + i)) {
Temporary = *(SourceArray + i);
*(SourceArray + i) = *(SourceArray + i - 1);
*(SourceArray + i - 1) = Temporary;
*Counter += 1; // Вычисление количества
} // перестановок. //
}
MinIndex++;
for (i = MinIndex; i<= MaxIndex; i++) {
if (*(SourceArray + i - 1) > * (SourceArray + i)) {
Temporary = *(SourceArray + i);
*(SourceArray + i) = *(SourceArray + i - 1);
*(SourceArray + i - 1) = Temporary;
*Counter += 1; // Вычисление количества
} // перестановок. //
}
MaxIndex--;
}
*Stopwatch = (clock () - *Stopwatch) / CLOCKS_PER_SEC; // Выключение STOPWATCH. //
} |
|
10/11. WriteArrayFunction.cpp:
C++ | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| /*
*Лабораторная работа: 10.
*Тема: Алгоритмы сортировки и оценка их сложности.
*Пункт: 5. Задание.
*Файл: Lab10_YaP_2019_1S.pdf
*
*Язык: C++.
*Среда: Microsoft Visual Studio 2019 v16.3.0.
*Платформа: x64.
*Изменение: 04.01.2020.
*
*Вариант: отсутствует.
*Защита: 27.12.2019.
*Задание: БН. (...)
*/
#include <iostream> // Требуется для PRINTF, CIN, COUT. //
#include "Header.h"
void WriteArrayFunction (int *SourceArray, int Dimension) { // Определение WRITEARRAYFUNCTION. //
int Choice = 0;
printf ("\nХотите вывести массив на экран?\n\n1) Да.........................1\n2) Нет........................2\n\nВаш выбор: ");
cin >> Choice;
if ((Choice < 1) || (Choice > 2)) {
MessageFunction ();
}
if (Choice == 1) {
printf ("\nЭлементы массива: ");
for (int i = 0; i < Dimension; i++) {
printf ("%4d ", *(SourceArray + i));
}
cout << endl;
}
} |
|
11/11. ExitProgramFunction.cpp:
C++ | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| /*
*Лабораторная работа: 10.
*Тема: Алгоритмы сортировки и оценка их сложности.
*Пункт: 5. Задание.
*Файл: Lab10_YaP_2019_1S.pdf
*
*Язык: C++.
*Среда: Microsoft Visual Studio 2019 v16.3.0.
*Платформа: x64.
*Изменение: 04.01.2020.
*
*Вариант: отсутствует.
*Защита: 27.12.2019.
*Задание: БН. (...)
*/
#include <iostream> // Требуется для SYSTEM, EXIT, PRINTF. //
#include "Header.h"
void ExitProgramFunction () { // Определение EXITPROGRAMNFUNCTION. //
system ("pause");
exit (true);
}
void MessageFunction () { // Определение MESSAGEFUNCTION. //
printf ("\nОшибка ввода. Программа завершает свою работу.\n\n");
ExitProgramFunction (); // Выводится на экран, если введен отсутствующий ответ. //
} |
|
|