Файл: Анпоо колледж воронежского института высоких технологий.docx

intN=data.Length;

// The intervals for the shell sort must be sorted, ascending

for(k=intervals.Length-1;k>=0;k--){

intinterval=intervals[k];

for(m=0;m
for(j=m+interval;j
for(i=j;i>=interval&&data[i]
exchange(data,i,i-interval);

}

}

}

}

}

publicstaticvoidIntArrayShellSortNaive(int[]data)

{

int[]intervals={1,2,4,8};

IntArrayShellSort(data,intervals);

}

Схема алгоритма для сортировки методом Шелла представлена ниже



Схема 1

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

---

Раздел 3

В результате работы программы мы получаем отсортированные данные. При этом время сортировки больших данных составляет O(n), при сортировке среднего и малого объёма данных составляет O(n log(n)), где n – длина массива данных. Другими словами, C# эффективен для сортировки больших списков и массивов, но для достижения этой цели требуется O(N) дополнительного пространства оперативной памяти компьютера во время выполнения алгоритма сортировки. Временная сложность составляет O(N*log N), поскольку используется стратегия «разделяй и властвуй».

Алгоритм сортирует большой массив данных за 25мкс (0,0025112 секунды), также сортирует малый массив данных за 17мкс (1,7012секунды).

Заключение

В данной работе были проанализированы методы внешней сортировки, их реализация в программном коде. На практике были применены полученные теоретические знания.

В целом, было выявлено, что хороший алгоритм внешней сортировки будет стремиться сделать следующее:

• 
  Сделать начальные прогоны как можно более длинными.
  
• 
  На всех этапах как можно больше перекрывать вход данных, обработку и их вывод.
  
• 
  Использовать как можно больше рабочей памяти. Использование большего объема памяти обычно ускоряет обработку. На самом деле, больше памяти даст больший эффект, чем более быстрый диск. Более быстрый процессор вряд ли даст значительное улучшение времени работы при внешней сортировке, поскольку скорость дискового ввода-вывода является ограничивающим фактором.
  

Список используемых источников

1. 
   Копылова, О. Ю. Сравнительный анализ методологий внешней сортировки / О. Ю. Копылова // Вестник современных исследований. – 2018. – № 6.1(21). – С. 411-413. – EDN XURJXF
   
2. 
   Самуйлов, Сергей Владимирович, Артем Олегович Денисов, and Владислав Юрьевич Дунаев. "Анализ алгоритмов внешней сортировки." In Управление реформированием социально-экономического развития предприятий, отраслей, регионов, pp. 268-269. 2018
   
3. 
   Апатова, Н. В. Datascience: алгоритмы сортировки / Н. В. Апатова // Актуальные проблемы и перспективы развития экономики : труды XIX Всероссийской с международным участием научнопрактической конференции, Симферополь-Гурзуф, 15–17 октября 2020 года. – Симферополь: ИП Зуева Т. В., 2020. – С. 4. – EDNEUYVMF
   
4. 
   Ерохин, В.В., 2018. Совершенствование параллельных вычислений в распределенной базе данных. Вестник современных исследований, (12.5), pp.121-129
   
5. 
   Заварыко, А.Ю. and Старцев, А.А., 2020. Использование реляционных баз данных в проектировании технологических процессов. Политехнический молодежный журнал, (10), pp.3-3
   
6. 
   Кнут, Дональд. Искусство программирования. Том 3. Сортировка и поиск. Litres, 2022
   

---

Приложение 2

using System;
	using System.Collections.Generic;
	using System.Linq;
	using System.Text;
	using System.Threading.Tasks;
	using System.Collections;
	namespace RekursiveSorts
	{
	class Program
	{
	static void Main(string[] args)
	{
	int[] a = new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
	ArraySort.BubbleSortRecursive(a, a.Length);
	ArraySort.Show(a);
	int[] b = new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
	ArraySort.SelectionSortRecursive(b, 0);
	ArraySort.Show(b);
	int[] c1 = new int[] { 9, 8, 4, 6, 5, 4, 3, 2, 1 };
	ArraySort.InsertionSortRecursiveByLength(c1, c1.Length);
	ArraySort.Show(c1);
	int[] c2 = new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
	ArraySort.InsertionSortRecursiveByIndex(c2, 0);
	ArraySort.Show(c2);
	int[] d1 = new int[] { 9, 8, 7, 7, 5, 4, 3, 5, 1 };
	ArraySort.Mergesort(d1, 0, d1.Length - 1);
	ArraySort.Show(d1);
	int[] d2 = new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
	ArraySort.MergeSort(d2, 0, d2.Length - 1);
	ArraySort.Show(d2);
	int[] e = new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
	ArraySort.QuickSort(e, 0, e.Length - 1);
	ArraySort.Show(e);
	int[] f = new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
	ArraySort.BinarySearch(f);
	ArraySort.Show(f);
	}
	}
	}

---

---

Файл ArraySort.cs 

using System;
	using System.Collections.Generic;
	using System.Linq;
	using System.Text;
	using System.Threading.Tasks;
	namespace RekursiveSorts
	{
	public static class ArraySort
	{
	public static void Show(int[] array)
	{
	foreach (var el in array)
	{
	Console.Write(el + " ");
	}
	Console.WriteLine("\n");
	}
	// 1.BubbleSort
	public static void BubbleSortRecursive(int[] array, int n)
	{
	if (n == 0)
	{
	return;
	}
	for (int j = 0; j < array.Length - 1; j++)
	{
	if (array[j] > array[j + 1])
	{
	int temp = array[j + 1];
	array[j + 1] = array[j];
	array[j] = temp;
	}
	}
	BubbleSortRecursive(array, n - 1);
	}
	// 2.SelectionSort //
	public static void SelectionSortRecursive(int[] array, int n)
	{
	if (n >= array.Length - 1)
	{
	return;
	}
	int minIndex = n;
	for (int i = n + 1; i < array.Length; i++)
	{
	if (array[i] < array[minIndex])
	{
	minIndex = i;
	}
	}
	int temp = array[n];
	array[n] = array[minIndex];
	array[minIndex] = temp;
	SelectionSortRecursive(array, n + 1);
	}
	// 3.InsertionSort//
	public static void InsertionSortRecursiveByIndex(int[] a, int i)
	{
	if (i == a.Length)
	{
	return;
	}
	while (i > 0 && a[i] < a[i - 1])
	{
	int temp = a[i];
	a[i] = a[i - 1];
	a[i - 1] = temp;
	i--;
	}
	InsertionSortRecursiveByIndex(a, i + 1);
	}
	public static void InsertionSortRecursiveByLength(int[] array, int n)
	{
	if (n <= 1)
	{
	return;
	}
	InsertionSortRecursiveByLength(array, n - 1);
	int last = array[n - 1];
	int j = n - 2;
	while (j >= 0 && array[j] > last)
	{
	array[j + 1] = array[j];
	j--;
	}
	array[j + 1] = last;
	}
	// 4.MergeSort //
	public static void Mergesort(int[] array, int beg, int end) // imy
	{
	if (beg == end)
	return;
	int mid = (beg + end) / 2;
	Mergesort(array, beg, mid);
	Mergesort(array, mid + 1, end);
	int i = beg;
	int j = mid + 1;
	int l = end - beg + 1;
	int[] temp = new int[l];
	for (int k = 0; k < l; k++)
	{
	if (j > end || (i <= mid && array[i] < array[j]))

---