Раздел 3
В результате работы программы мы получаем отсортированные данные. При этом время сортировки больших данных составляет O(n), при сортировке среднего и малого объёма данных составляет O(n log(n)), где n – длина массива данных. Другими словами, C# эффективен для сортировки больших списков и массивов, но для достижения этой цели требуется O(N) дополнительного пространства оперативной памяти компьютера во время выполнения алгоритма сортировки. Временная сложность составляет O(N*log N), поскольку используется стратегия «разделяй и властвуй».
Алгоритм сортирует большой массив данных за 25мкс (
0,0025112 секунды), также сортирует малый массив данных за 17мкс (1,7012секунды).
Заключение
В данной работе были проанализированы методы внешней сортировки, их реализация в программном коде. На практике были применены полученные теоретические знания.
В целом, было выявлено, что хороший алгоритм внешней сортировки будет стремиться сделать следующее:
Сделать начальные прогоны как можно более длинными.
На всех этапах как можно больше перекрывать вход данных, обработку и их вывод.
Использовать как можно больше рабочей памяти. Использование большего объема памяти обычно ускоряет обработку. На самом деле, больше памяти даст больший эффект, чем более быстрый диск. Более быстрый процессор вряд ли даст значительное улучшение времени работы при внешней сортировке, поскольку скорость дискового ввода-вывода является ограничивающим фактором.
Список используемых источников
Копылова, О. Ю. Сравнительный анализ методологий внешней сортировки / О. Ю. Копылова // Вестник современных исследований. – 2018. – № 6.1(21). – С. 411-413. – EDN XURJXF
Самуйлов, Сергей Владимирович, Артем Олегович Денисов, and Владислав Юрьевич Дунаев. "Анализ алгоритмов внешней сортировки." In Управление реформированием социально-экономического развития предприятий, отраслей, регионов, pp. 268-269. 2018
Апатова, Н. В. Datascience: алгоритмы сортировки / Н. В. Апатова // Актуальные проблемы и перспективы развития экономики : труды XIX Всероссийской с международным участием научнопрактической конференции, Симферополь-Гурзуф, 15–17 октября 2020 года. – Симферополь: ИП Зуева Т. В., 2020. – С. 4. – EDNEUYVMF
Ерохин, В.В., 2018. Совершенствование параллельных вычислений в распределенной базе данных. Вестник современных исследований, (12.5), pp.121-129
Заварыко, А.Ю. and Старцев, А.А., 2020. Использование реляционных баз данных в проектировании технологических процессов. Политехнический молодежный журнал, (10), pp.3-3
Кнут, Дональд. Искусство программирования. Том 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);
|
|
}
|
|
}
|
|
}
| |
Скачать 440.67 Kb.