Участник:Bkmish/Сортировка слиянием (последовательный и параллельный варианты): различия между версиями

Версия 22:59, 29 октября 2023

Содержание

1 Свойства и структура алгоритмов
2 Программная реализация алгоритма
3 Литература

1 Свойства и структура алгоритмов

1.1 Общее описание алгоритма

Алгоритм сортировки слиянием (англ. merge sort) является методом упорядочивания списков или других структур данных, в которых доступ к элементам может быть получен только последовательно. Этот алгоритм был разработан Джоном фон Нейманом в 1945 году и является хорошим примером использования принципа «разделяй и властвуй», поскольку основан на разбиении главной задачи на более мелкие подзадачи, которые решаются, например, с помощью рекурсивного вызова или непосредственно, если количество элементов рассматриваемой структуры достаточно мало. После этого полученные результаты комбинируются для получения решения основной задачи.

Последовательная версия алгоритма сортировки слиянием имеет временную сложность [math]\Theta(n \log n)[/math] в лучшем, среднем и худшем случаях. Это происходит потому, что алгоритм разделяет массив на две половины на каждом уровне рекурсии (что требует [math]\log n[/math] уровней), а затем сливает [math]n[/math] элементов на каждом уровне, что дает общую временную сложность [math]\Theta(n \log n)[/math]

Параллельная версия алгоритма сортировки слиянием может быть выполнена с использованием различных подходов и, следовательно, имеет различные временные сложности. Так, например, используя один из алгоритмов распараллеливания, можно достичь сложности [math]\Theta \left(\frac{n}{(\log n)^2}\right)[/math]

1.2 Математическое описание алгоритма

В общем виде алгоритм сортировки слиянием выглядит следующим образом:

Разделение: исходный массив разделяется на две равные или приближенно равные части. Если массив состоит из одного элемента, он считается отсортированным. Если массив содержит более одного элемента, процесс разделения продолжается рекурсивно, пока в подмассивах не останется по одному элементу, такие подмассивы по определению считаются отсортированными.
Сортировка и слияние: отсортированные подмассивы сливаются в один. Процесс слияния осуществляется путем сравнения первых элементов каждого подмассива. Меньший элемент перемещается в результирующий массив, и индекс в соответствующем подмассиве увеличивается на единицу. Этот процесс продолжается, пока не будут исчерпаны все элементы в обоих подмассивах

1.3 Вычислительное ядро алгоритма

Вычислительное ядро алгоритма сортировки слиянием − это процесс (состоящий из сравнений элементов и перемещения оставшихся элементов) слияния двух отсортированных подмассивов в один отсортированный массив. Этот процесс занимает большую часть времени работы алгоритма.

1.4 Макроструктура алгоритма

1.5 Схема реализации последовательного алгоритма

1.6 Последовательная сложность алгоритма

1.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

1.9 Входные и выходные данные алгоритма

1.10 Свойства алгоритма

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

3 Литература

Левитин А. В. Глава 4. Метод декомпозиции: Сортировка слиянием // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 169—172. — 576 с. — ISBN 978-5-8459-0987-9
Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.
Victor J. Duvanenko "Parallel Merge Sort" Dr. Dobb's Journal & blog
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4. (p. 797-805)

@@ Строка 5: / Строка 5: @@
 Алгоритм '''сортировки слиянием''' (англ. ''merge sort'') является методом упорядочивания списков или других структур данных, в которых доступ к элементам может быть получен только последовательно. Этот алгоритм был разработан Джоном фон Нейманом в 1945 году и является хорошим примером использования принципа «разделяй и властвуй», поскольку основан на разбиении главной задачи на более мелкие подзадачи, которые решаются, например, с помощью рекурсивного вызова или непосредственно, если количество элементов рассматриваемой структуры достаточно мало. После этого полученные результаты комбинируются для получения решения основной задачи.
-'''Последовательная версия''' алгоритма сортировки слиянием имеет временную сложность <math display="inline">\Theta(n \log n)</math> в лучшем, среднем и худшем случаях. Это происходит потому, что алгоритм разделяет массив на две половины на каждом уровне рекурсии (что требует <math>\log n</math> уровней), а затем сливает n элементов на каждом уровне, что дает общую временную сложность <math display="inline">\Theta(n \log n)</math>
+'''Последовательная версия''' алгоритма сортировки слиянием имеет временную сложность <math display="inline">\Theta(n \log n)</math> в лучшем, среднем и худшем случаях. Это происходит потому, что алгоритм разделяет массив на две половины на каждом уровне рекурсии (что требует <math>\log n</math> уровней), а затем сливает <math>n</math> элементов на каждом уровне, что дает общую временную сложность <math display="inline">\Theta(n \log n)</math>
 '''Параллельная версия''' алгоритма сортировки слиянием может быть выполнена с использованием различных подходов и, следовательно, имеет различные временные сложности. Так, например, используя один из алгоритмов распараллеливания, можно достичь сложности <math display="inline">\Theta \left(\frac{n}{(\log n)^2}\right)</math>