Уровень сложности – базовый. Провести сравнение указанных алгоритмов сортировки массивов, содержащих N1, N2, N3 и N4 элементов, по указанному в вариативной части критерию и объему требуемой дополнительно памяти.

Порядок: по убыванию элементов. Методы: простых вставок, бинарных вставок, Шелла (шаг сортировки ). N1=10000, N2=30000, N3=70000, N4=100000. Критерий – количество сравнений.

• Алгоритм сортировки методом простых вставок: для каждого элемента массива производится поиск подходящего места в уже упорядоченной части.

Трудоемкость сортировки методом простых вставок по количеству сравнений:

Случай	Ситуация, соответст—вующая случаю	Обоснование	Ожидаемое число сравнений элементов массива	Асимптотическая оценка сложности по количеству сравнений	Ожидаемое число вспомогат. сравнений
наилучший	массив упорядочен		(n-1) N1: 9999 N2: 29999 N3: 69999 N4: 99999	Ω(n)	2n-1 N1:19999 N2:59999 N3:139999 N4:199999
наихудший	массив упорядочен в обратном порядке		N1:49995000 N2:449985000 N3:2449965000 N4:4999950000	O(n2)	N1: 50014999 N2: 450044999 N3: 2450104999 N4:10000299999
средний	неупорядо-ченный массив		N1:24997500 N2:224992500 N3:1224982500 N4:2499975000	O(n2)	N1: 25017499 N2: 225052499 N3: 1225122499 N4: 2500174999

Пространственная сложность – O(1) (две переменных цикла и вспомогательная переменная).

• Алгоритм сортировки бинарными вставками: похож на сортировку простыми вставками, но вместо использования линейного поиска для поиска местоположения, в которое должен быть вставлен элемент, используется двоичный поиск.

Трудоемкость сортировки бинарными вставками по количеству сравнений:

 

 

Случай	Ситуация, соответст—вующая случаю	Обоснование	Ожидаемое число сравнений элементов массива	Асимптотическая оценка сложности по количеству сравнений	Ожидаемое число вспомогат. сравнений
наилучший	массив упорядочен		N1: 9999 N2: 29999 N3: 69999 N4: 99999	Ω(n)	n   N1: 100 N2: 500 N3: 1000 N4: 2000
наихудший	массив упорядочен в обратном порядке		N1:49995000 N2:449985000 N3:2449965000 N4:4999950000	O(n2)	(n2-n)/2   N1: 4950 N2: 124750 N3: 499500 N4: 1999000
средний	неупорядо-ченный массив		N1:24997500 N2:224992500 N3:1224982500 N4:2499975000	O(n2)	(n2-n)/4   N1: 2475 N2: 62 375 N3: 249750 N4: 999500

Пространственная сложность – O(n+m), где m – мощность алфавита (массив для сохранения элементов массива в новом порядке и массив счетчиков).

• Алгоритм сортировки Шелла: сначала сравниваются и сортируются между собой значения, стоящие один от другого на некотором расстоянии. После этого процедура повторяется для некоторых меньших значений {\displaystyle d}расстояний, а завершается сортировка Шелла упорядочиванием элементов при {\displaystyle d=1}расстоянии равном единице.

Трудоемкость сортировки Шелла по количеству сравнений:

Случай	Ситуация, соответст—вующая случаю	Обоснование	Ожидаемое число сравнений элементов массива	Асимптотическая оценка сложности по количеству сравнений	Ожидаемое число вспомогат. сравнений
наилучший	массив упорядочен		N1: 9999 N2: 29999 N3: 69999 N4: 99999	Ω(n)	n   N1: 100 N2: 500 N3: 1000 N4: 2000
наихудший	массив упорядочен в обратном порядке		N1:49995000 N2:449985000 N3:2449965000 N4:4999950000	O(n2)	(n2-n)/2   N1: 4950 N2: 124750 N3: 499500 N4: 1999000
средний	неупорядо-ченный массив		N1:24997500 N2:224992500 N3:1224982500 N4:2499975000	O(n2)	(n2-n)/4   N1: 2475 N2: 62 375 N3: 249750 N4: 999500

Пространственная сложность – O(1) (две переменных цикла и вспомогательная переменная).

• Алгоритм сортировки Шелла: сначала сравниваются и сортируются между собой значения, стоящие один от другого на некотором расстоянии. После этого процедура повторяется для некоторых меньших значений {\displaystyle d}расстояний, а завершается сортировка Шелла упорядочиванием элементов при {\displaystyle d=1}расстоянии равном единице.

Трудоемкость сортировки Шелла по количеству сравнений:

Случай	Ситуация, соответст—вующая случаю	Обоснование	Ожидаемое число сравнений элементов массива	Асимптотическая оценка сложности по количеству сравнений	Ожидаемое число вспомогат. сравнений
наилучший	массив упорядочен		N1: 9999 N2: 29999 N3: 69999 N4: 99999	Ω(n)	n   N1: 100 N2: 500 N3: 1000 N4: 2000
наихудший	массив упорядочен в обратном порядке		N1:49995000 N2:449985000 N3:2449965000 N4:4999950000	O(n2)	(n2-n)/2   N1: 4950 N2: 124750 N3: 499500 N4: 1999000
средний	неупорядо-ченный массив		N1:24997500 N2:224992500 N3:1224982500 N4:2499975000	O(n2)	(n2-n)/4   N1: 2475 N2: 62 375 N3: 249750 N4: 999500

Пространственная сложность – O(1) (две переменных цикла и вспомогательная переменная).

Текст программы:

#include <iostream>

#include <windows.h>

#include <fstream>

#include <string>

#include <chrono>

#define TOTALSIZE 4

#define N1 10000

#define N2 30000

#define N3 70000

#define N4 100000

/*#define N1 3

#define N2 5

#define N3 7

#define N4 10*/

 

using namespace std;

using namespace std::chrono;

unsigned long int comp_main = 0, comp_add = 0;

unsigned long int memory;

 

void copy_array(int** arr, int** sort_arr, int* arr_size);

void make(int** arr, int* arr_size);

void full(int** arr, int* arr_size);

void get_arr(int* arr, int size);

void reverse(int* a, int n);

void StraightInsertion(int* a, int n);

void BinaryInsertion(int* a, int n);

void ShellSort(int* a, int n);

void ShellSort1(int* a, int n);

 

 

 

int main()

{

SetConsoleOutputCP(1251);

char NameSort[4][40] = { «Сортировка вставками», «Сортировка бинарными вставками», «Сортировка Шелла с шагом 1», «Сортировка Шелла с шагом 2» };

void(*func[4])(int*, int) = { StraightInsertion, BinaryInsertion, ShellSort, ShellSort1 };

int i = 0, sizes[TOTALSIZE] = {N1, N2, N3, N4};

string str;

ifstream file;

file.open(«test_numbers.txt»);

if (!file.is_open())

cout << «Ошибка открытия файла» << endl;

else

{

cout << «Файл открыт» << endl;

int** array_orig = new int* [12];

int** array_sort = new int* [12];

make(array_orig, sizes);

make(array_sort, sizes);

full(array_orig, sizes);

for (int j = 0; j < 4; j++)

{

cout << endl << » » << NameSort[j] << endl;

copy_array(array_orig, array_sort, sizes);

for (int i = 0; i < 12; i++)

{

memory = 0;

auto start = high_resolution_clock::now();

comp_main = 0, comp_add = 0;

func[j](array_sort[i], sizes[i / 3]);

auto end = high_resolution_clock::now();

auto duration = duration_cast<seconds>(end — start);

if (!(i % 3))

{

cout << «\nКоличество элементов: » << sizes[i / 3] << endl;

}

cout << «\tОсновные сравнения: » << comp_main << «\tВспомогательные сравнения: » << comp_add << «\tВремя выполнения: » << duration.count() << «\tПамять: » << memory << endl;

}

}

}

return 0;

}

 

void copy_array(int** arr, int** sort_arr, int* arr_size)

{

int size;

for (int cur_size = 0; cur_size < TOTALSIZE; cur_size++)

{

size = arr_size[cur_size];

memcpy(sort_arr[cur_size * 3], arr[cur_size * 3], size * (sizeof(int)));

memcpy(sort_arr[cur_size * 3 + 1], arr[cur_size * 3 + 1], size * (sizeof(int)));

memcpy(sort_arr[cur_size * 3 + 2], arr[cur_size * 3 + 2], size * (sizeof(int)));

}

}

 

void make(int** arr, int* arr_size)

{

int size, cur_arr = 0;

for (int curSize = 0; curSize < TOTALSIZE; curSize++)

{

size = arr_size[curSize];

for (int counter = 0; counter < 3; counter++)

{

arr[cur_arr] = new int[size];

cur_arr++;

}

}

}

 

void full(int** arr, int* arr_size)

{

int size;

for (int cur_size = 0; cur_size < TOTALSIZE; cur_size++)

{

size = arr_size[cur_size];

get_arr(arr[cur_size * 3], size);

memcpy(arr[cur_size * 3 + 1], arr[cur_size * 3], size * (sizeof(int)));

ShellSort(arr[cur_size * 3 + 1], size);

memcpy(arr[cur_size * 3 + 2], arr[cur_size * 3 + 1], size * (sizeof(int)));

reverse(arr[cur_size * 3 + 2], size);

}

}

 

void get_arr(int* arr, int size)

{

ifstream f;

f.open(«test_numbers.txt»);

for (int* i = arr; i != arr + size; i++)

{

f >> *i;

}

f.close();

}

 

 

/* разворот массива*/

void reverse(int* a, int n)

{

int i, j, tmp;

for (i = 0, j = n — 1; i < j; i++, j—)

if (a[i] != a[j])

{

tmp = a[i];

a[i] = a[j];

a[j] = tmp;

}

}

 

/* сортировкa вставками */

void StraightInsertion(int* a, int n) /*адрес начала массива, его размер, размер уже упорядоченной части*/

{

int i, j, x;

memory = sizeof(int) * 3;

for (i = 1; ++comp_add && i < n; i++)

{

x = a[i];

for (j = i; ++comp_add && j && ++comp_main && x > a[j — 1]; j—)

{

a[j] = a[j — 1];

}

a[j] = x;

}

 

}

 

/* сортировка бинарными вставками */

void BinaryInsertion(int* a, int n)

{

int i, j, m, left, right, x;

memory = sizeof(int) * 6;

for (i = 1; ++comp_add && i < n; i++)

{

x = a[i]; left = i; right = 0;

while (++comp_add && left > right) /*пока есть что просматривать*/

{

m = (left + right) / 2; /*делим интервал поиска пополам*/

if (++comp_main && a[m] < x) /*если вставляемое значение больше текущего */

left = m; /*искать надо в правой части*/

else

right = m + 1; /*а если нет, то будем искать в левой*/

}

for (j = i — 1; ++comp_add && j >= left; j—)

a[j + 1] = a[j];

a[left] = x;

}

}

 

/* сортировка Шелла (шаг h[m]=3h[m+1]+1, h[t]=1, t=log3n-1) */

void ShellSort(int* a, int n)

{

const int t = (int)(log(n) / log(3));

int i, j, k, m, x;

int* h = (int*)malloc(t * sizeof(int));

memory = sizeof(int) * 5 + sizeof(const int) + t * sizeof(h);

h[t — 1] = 1;

for (m = t — 2; ++comp_add && m >= 0; m—)

h[m] = h[m + 1] * 3 + 1;

for (m = 0; ++comp_add && m < t; m++) /*последовательно перебираем все расстояния*/

{

k = h[m];

for (i = k; ++comp_add && i < n; i++) /*до конца цикла метод вставки с учетом шага h[m]*/

{

x = a[i]; j = i — k;

while (++comp_add && j >= 0 && ++comp_main && x > a[j])

{

a[j + k] = a[j];

j -= k;

}

a[j + k] = x;

}

}

free(h);

}

 

/* сортировка Шелла (шаг h[m]=2h[m+1]+1, h[t]=1, t=log2n-1) */

void ShellSort1(int* a, int n)

{

const int t = (int)(log(n) / log(2));

int i, j, k, m, x;

int* h = (int*)malloc(t * sizeof(int));

memory = sizeof(int) * 5 + sizeof(const int) + t * sizeof(h);

h[t — 1] = 1;

for (m = t — 2; ++comp_add && m >= 0; m—)

h[m] = h[m + 1] * 2 + 1;

for (m = 0; ++comp_add && m < t; m++) /*последовательно перебираем все расстояния*/

{

k = h[m];

for (i = k; ++comp_add && i < n; i++) /*до конца цикла метод вставки с учетом шага h[m]*/

{

x = a[i]; j = i — k;

while (++comp_add && j >= 0 && ++comp_main && x > a[j])

{

a[j + k] = a[j];

j -= k;

}

a[j + k] = x;

}

}

free(h);

}

Результаты работы программы:

Скриншоты с пояснительным текстом

Анализ полученных данных:

Сравниваем полученные результаты с расчетными, делаем выводы.

Для каждого алгоритма сравниваем количество основных операций с количеством вспомогательных, делаем выводы.

Сравниваем между собой трудоемкости анализируемых алгоритмов сортировки по асимптотике и по полученным программно результатам (в лучшем худшем и среднем случаях), делаем выводы.

Сравниваем между собой время работы рассматриваемых алгоритмов (в лучшем, среднем и худшем случаях), соотносим их с количеством подсчитанных операций, делаем выводы.

Сравниваем пространственную сложность анализируемых алгоритмов, соотносим ее с полученным временем сортировки, делаем выводы.

При выполнении задания на повышенном уровне сложности анализируем результаты, полученные для последовательностей с повторяющимися ключами, и сравниваем их со сделанным ранее прогнозом, делаем выводы.

Вывод: по результатам проведенного анализа самым эффективным из рассмотренных алгоритмов по соотношению время-память является алгоритм сортировки методом случайных перестановок.