Алговики - Вклад [ru]

Участник:Kiryan/Алгоритм сортировки слиянием

2025-11-27T07:30:11Z

Kiryan:

Основные авторы описания: [[Участник:Kiryan|К.Е.Деревянкин]].
== Свойства и структура алгоритмов ==
'''
=== Общее описание алгоритма ===
'''
'''Сортировка слиянием''' (англ. ''merge sort'') — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

Алгоритм был изобретён Джоном фон Нейманом в 1945 году
'''
=== Математическое описание алгоритма ===
'''
Пусть задано множество элементов: S = {a1, a2, ..., an} с определенным на нем отношением линейного порядка ≤. Требуется найти такую перестановку π ∈ Sn, что:∀i,j ∈ {1, 2, ..., n}: i < j ⇒ aπ(i) ≤ aπ(j)

Алгоритм реализует стратегию «разделяй и властвуй», состоящую из трех этапов:

# Разделение: Исходный массив рекурсивно делится на две примерно равные части до достижения базового случая (массивы длины 1)
# Упорядочивание: Базовые случаи (массивы длины 1) по определению являются отсортированными
# Слияние: Отсортированные подмассивы объединяются в один отсортированный массив

Операция разделения: SPLIT(A, p, r) = (A[p..q], A[q+1..r]), где q = ⌊(p + r)/2⌋

Операция слияния: MERGE(L, R) = S, где L и R — отсортированные массивы, S — отсортированный массив, содержащий все элементы L и R.
'''
=== Вычислительное ядро алгоритма ===
'''
Вычислительное ядро алгоритма составляет процедура слияния двух отсортированных массивов, которая выполняется на каждом уровне рекурсии и определяет общую производительность алгоритма.
'''
=== Макроструктура алгоритма ===
'''
Алгоритм сортировки слиянием реализует стратегию «разделяй и властвуй» (divide and conquer) и состоит из трех макрофаз:
# Разделения (Divide). Рекурсивная декомпозиция на подмассивы
# Базовые случаи (Conquer). Обработка тривиальных подзадач
# Слияние (Combine). Иерархическое объединение результатов
'''

=== Схема реализации последовательного алгоритма ===
'''
Пусть задан массив
A = [a1, a2, ..., an], ai ∈ R, i = 1, ...,n,
требующий сортировки по возрастанию.

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

=== Последовательная сложность алгоритма ===
'''
На каждом шаге массив размером n делится на две части, каждая из которых рекурсивно сортируется, после чего выполняется операция слияния двух отсортированных подмассивов.

Рекуррентное соотношение для оценки времени работы алгоритма имеет вид:

T(n) = 2T(n/2) + O(n), где O(n) — затраты времени на слияние двух половин массива.

Последовательная временная сложность сортировки слиянием: T(n) = O(nlogn).
'''

=== Информационный граф ===
'''
[[File:Merge_sort.png|800px]]
'''

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

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

'''

=== Входные и выходные данные алгоритма ===
'''
На вход алгоритму подаётся:

* Одномерный массив чисел длиной N, который требуется отсортировать по возрастанию A=[a1,a2,a3,…,aN]
* Количество процессов P, участвующих в вычислении

На выходе алгоритма формируется отсортированный массив длиной N:

A′ = [a'1, a'2, a'3, … , a'N], a'1 ≤ a'2 ≤ ⋯ ≤ a'N
'''

=== Свойства алгоритма ===
'''
Алгоритм сортировки слиянием относится к классу рекурсивных алгоритмов типа «разделяй и властвуй» (divide and conquer).
Параллельная версия основана на независимой обработке подмножеств данных и их последующем слиянии.

Алгоритм реализует параллелизм по данным — каждый процесс сортирует свою часть массива независимо от других.
#

== Программная реализация алгоритма ==
'''
=== Особенности реализации последовательного алгоритма ===
'''

Последовательный алгоритм сортировки слиянием основан на принципе «разделяй и властвуй» и включает рекурсивное разбиение массива на две части до подмассивов размера 1. На каждом шаге используется вспомогательная память для копирования левой и правой части массива, после чего выполняется операция слияния, работающая за линейное время. Алгоритм является стабильным и полностью детерминированным, а его асимптотическая сложность составляет O(nlogn). Благодаря независимости обработки левого и правого подмассивов данная реализация хорошо подходит для последующей параллелизации.

'''

=== Возможные способы и особенности параллельной реализации алгоритма ===
'''
Параллельная реализация сортировки слиянием основана на том, что сортировка левой и правой части массива выполняется независимо, что делает алгоритм естественно распараллеливаемым. Основной принцип параллельной версии заключается в создании отдельных задач (threads или процессов), отвечающих за сортировку подмассивов на различных уровнях рекурсивного дерева.
'''

=== Результаты прогонов ===
'''

Результаты выполнения параллельной сортировки слиянием на различных вычислительных платформах

Массив из 100 млн. элементов

Локальный компьютер (8 потоков OpenMP)

Команда: OMP_NUM_THREADS=8 ./mergesort_omp

Результат: 9.01 сек

СК «Ломоносов-2» (8 потоков OpenMP, очередь test)

Команда: sbatch -p test -n 1 --cpus-per-task=8 job_omp_8.sh

Результат: 11.02 сек

Массив из 1 млрд. элементов

Локальный компьютер (8 потоков OpenMP)

Команда: OMP_NUM_THREADS=8 ./mergesort_omp

Результат: не справился с работой

СК «Ломоносов-2» (8 потоков OpenMP, очередь test)

Команда: sbatch -p test -n 1 --cpus-per-task=8 job_omp_8.sh

Результат: 85.9 сек

Исследование масштабируемости на СК «Ломоносов-2»:

Массив 1 млрд. элементов

1 поток: 213,78 сек

2 потока: 178,246 сек

4 потока: 120,722 сек

8 потоков: 88,04 сек

14 потоков: 73,336 сек

'''
=== Выводы для классов архитектур ===
'''
Сортировка слиянием хорошо масштабируется на MIMD- и гибридных архитектурах благодаря независимому выполнению подзадач. На SIMD-архитектурах её эффективность ограничена, а на SISD работает предсказуемо, но без ускорения. На распределённых системах ключевым фактором становится оптимизация объёма межпроцессных обменов.
#

== Литература ==
Knuth D.E. The Art of Computer Programming. Volume 3: Sorting and Searching. – 2nd ed. – Addison-Wesley, 1998. – 780 p.

Участник:Kiryan/Алгоритм сортировки слиянием

2025-11-27T07:28:37Z

Kiryan:

Основные авторы описания: [[Участник:Kiryan|К.Е.Деревянкин]].
== Свойства и структура алгоритмов ==
'''
=== Общее описание алгоритма ===
'''
'''Сортировка слиянием''' (англ. ''merge sort'') — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

Алгоритм был изобретён Джоном фон Нейманом в 1945 году
'''
=== Математическое описание алгоритма ===
'''
Пусть задано множество элементов: S = {a1, a2, ..., an} с определенным на нем отношением линейного порядка ≤. Требуется найти такую перестановку π ∈ Sn, что:∀i,j ∈ {1, 2, ..., n}: i < j ⇒ aπ(i) ≤ aπ(j)

Алгоритм реализует стратегию «разделяй и властвуй», состоящую из трех этапов:

# Разделение: Исходный массив рекурсивно делится на две примерно равные части до достижения базового случая (массивы длины 1)
# Упорядочивание: Базовые случаи (массивы длины 1) по определению являются отсортированными
# Слияние: Отсортированные подмассивы объединяются в один отсортированный массив

Операция разделения: SPLIT(A, p, r) = (A[p..q], A[q+1..r]), где q = ⌊(p + r)/2⌋

Операция слияния: MERGE(L, R) = S, где L и R — отсортированные массивы, S — отсортированный массив, содержащий все элементы L и R.
'''
=== Вычислительное ядро алгоритма ===
'''
Вычислительное ядро алгоритма составляет процедура слияния двух отсортированных массивов, которая выполняется на каждом уровне рекурсии и определяет общую производительность алгоритма.
'''
=== Макроструктура алгоритма ===
'''
Алгоритм сортировки слиянием реализует стратегию «разделяй и властвуй» (divide and conquer) и состоит из трех макрофаз:
# Разделения (Divide). Рекурсивная декомпозиция на подмассивы
# Базовые случаи (Conquer). Обработка тривиальных подзадач
# Слияние (Combine). Иерархическое объединение результатов
'''

=== Схема реализации последовательного алгоритма ===
'''
Пусть задан массив
A = [a1, a2, ..., an], ai ∈ R, i = 1, ...,n,
требующий сортировки по возрастанию.

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

=== Последовательная сложность алгоритма ===
'''
На каждом шаге массив размером n делится на две части, каждая из которых рекурсивно сортируется, после чего выполняется операция слияния двух отсортированных подмассивов.

Рекуррентное соотношение для оценки времени работы алгоритма имеет вид:

T(n) = 2T(n/2) + O(n), где O(n) — затраты времени на слияние двух половин массива.

Последовательная временная сложность сортировки слиянием: T(n) = O(nlogn).
'''

=== Информационный граф ===
'''
[[File:Merge_sort.png|800px]]
'''

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

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

'''

=== Входные и выходные данные алгоритма ===
'''
На вход алгоритму подаётся:

* Одномерный массив чисел длиной N, который требуется отсортировать по возрастанию A=[a1,a2,a3,…,aN]
* Количество процессов P, участвующих в вычислении

На выходе алгоритма формируется отсортированный массив длиной N:

A′ = [a'1, a'2, a'3, … , a'N], a'1 ≤ a'2 ≤ ⋯ ≤ a'N
'''

=== Свойства алгоритма ===
'''
Алгоритм сортировки слиянием относится к классу рекурсивных алгоритмов типа «разделяй и властвуй» (divide and conquer).
Параллельная версия основана на независимой обработке подмножеств данных и их последующем слиянии.

Алгоритм реализует параллелизм по данным — каждый процесс сортирует свою часть массива независимо от других.
#

== Программная реализация алгоритма ==
'''
=== Особенности реализации последовательного алгоритма ===
'''

Последовательный алгоритм сортировки слиянием основан на принципе «разделяй и властвуй» и включает рекурсивное разбиение массива на две части до подмассивов размера 1. На каждом шаге используется вспомогательная память для копирования левой и правой части массива, после чего выполняется операция слияния, работающая за линейное время. Алгоритм является стабильным и полностью детерминированным, а его асимптотическая сложность составляет O(nlogn). Благодаря независимости обработки левого и правого подмассивов данная реализация хорошо подходит для последующей параллелизации.

'''

=== Возможные способы и особенности параллельной реализации алгоритма ===
'''
Параллельная реализация сортировки слиянием основана на том, что сортировка левой и правой части массива выполняется независимо, что делает алгоритм естественно распараллеливаемым. Основной принцип параллельной версии заключается в создании отдельных задач (threads или процессов), отвечающих за сортировку подмассивов на различных уровнях рекурсивного дерева.
'''

=== Результаты прогонов ===
'''

Результаты выполнения параллельной сортировки слиянием на различных вычислительных платформах
Массив из 100 млн. элементов
Локальный компьютер (8 потоков OpenMP)
Команда: OMP_NUM_THREADS=8 ./mergesort_omp
Результат: 9.01 сек
СК «Ломоносов-2» (8 потоков OpenMP, очередь test)
Команда: sbatch -p test -n 1 --cpus-per-task=8 job_omp_8.sh
Результат: 11.02 сек
Массив из 1 млрд. элементов
Локальный компьютер (8 потоков OpenMP)
Команда: OMP_NUM_THREADS=8 ./mergesort_omp
Результат: не справился с работой
СК «Ломоносов-2» (8 потоков OpenMP, очередь test)
Команда: sbatch -p test -n 1 --cpus-per-task=8 job_omp_8.sh
Результат: 85.9 сек
Исследование масштабируемости на СК «Ломоносов-2»:
Массив 1 млрд. элементов
1 поток: 213,78 сек
2 потока: 178,246 сек
4 потока: 120,722 сек
8 потоков: 88,04 сек
14 потоков: 73,336 сек

'''
=== Выводы для классов архитектур ===
'''
Сортировка слиянием хорошо масштабируется на MIMD- и гибридных архитектурах благодаря независимому выполнению подзадач. На SIMD-архитектурах её эффективность ограничена, а на SISD работает предсказуемо, но без ускорения. На распределённых системах ключевым фактором становится оптимизация объёма межпроцессных обменов.
#

== Литература ==
Knuth D.E. The Art of Computer Programming. Volume 3: Sorting and Searching. – 2nd ed. – Addison-Wesley, 1998. – 780 p.

Участник:Kiryan/Алгоритм сортировки слиянием

2025-11-25T15:17:28Z

Kiryan:

Основные авторы описания: [[Участник:Kiryan|К.Е.Деревянкин]].
== Свойства и структура алгоритмов ==
'''
=== Общее описание алгоритма ===
'''
'''Сортировка слиянием''' (англ. ''merge sort'') — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

Алгоритм был изобретён Джоном фон Нейманом в 1945 году
'''
=== Математическое описание алгоритма ===
'''
Пусть задано множество элементов: S = {a1, a2, ..., an} с определенным на нем отношением линейного порядка ≤. Требуется найти такую перестановку π ∈ Sn, что:∀i,j ∈ {1, 2, ..., n}: i < j ⇒ aπ(i) ≤ aπ(j)

Алгоритм реализует стратегию «разделяй и властвуй», состоящую из трех этапов:

# Разделение: Исходный массив рекурсивно делится на две примерно равные части до достижения базового случая (массивы длины 1)
# Упорядочивание: Базовые случаи (массивы длины 1) по определению являются отсортированными
# Слияние: Отсортированные подмассивы объединяются в один отсортированный массив

Операция разделения: SPLIT(A, p, r) = (A[p..q], A[q+1..r]), где q = ⌊(p + r)/2⌋

Операция слияния: MERGE(L, R) = S, где L и R — отсортированные массивы, S — отсортированный массив, содержащий все элементы L и R.
'''
=== Вычислительное ядро алгоритма ===
'''
Вычислительное ядро алгоритма составляет процедура слияния двух отсортированных массивов, которая выполняется на каждом уровне рекурсии и определяет общую производительность алгоритма.
'''
=== Макроструктура алгоритма ===
'''
Алгоритм сортировки слиянием реализует стратегию «разделяй и властвуй» (divide and conquer) и состоит из трех макрофаз:
# Разделения (Divide). Рекурсивная декомпозиция на подмассивы
# Базовые случаи (Conquer). Обработка тривиальных подзадач
# Слияние (Combine). Иерархическое объединение результатов
'''

=== Схема реализации последовательного алгоритма ===
'''
Пусть задан массив
A = [a1, a2, ..., an], ai ∈ R, i = 1, ...,n,
требующий сортировки по возрастанию.

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

=== Последовательная сложность алгоритма ===
'''
На каждом шаге массив размером n делится на две части, каждая из которых рекурсивно сортируется, после чего выполняется операция слияния двух отсортированных подмассивов.

Рекуррентное соотношение для оценки времени работы алгоритма имеет вид:

T(n) = 2T(n/2) + O(n), где O(n) — затраты времени на слияние двух половин массива.

Последовательная временная сложность сортировки слиянием: T(n) = O(nlogn).
'''

=== Информационный граф ===
'''
[[File:Merge_sort.png|800px]]
'''

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

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

'''

=== Входные и выходные данные алгоритма ===
'''
На вход алгоритму подаётся:

* Одномерный массив чисел длиной N, который требуется отсортировать по возрастанию A=[a1,a2,a3,…,aN]
* Количество процессов P, участвующих в вычислении

На выходе алгоритма формируется отсортированный массив длиной N:

A′ = [a'1, a'2, a'3, … , a'N], a'1 ≤ a'2 ≤ ⋯ ≤ a'N
'''

=== Свойства алгоритма ===
'''
Алгоритм сортировки слиянием относится к классу рекурсивных алгоритмов типа «разделяй и властвуй» (divide and conquer).
Параллельная версия основана на независимой обработке подмножеств данных и их последующем слиянии.

Алгоритм реализует параллелизм по данным — каждый процесс сортирует свою часть массива независимо от других.
#

== Программная реализация алгоритма ==
'''
=== Особенности реализации последовательного алгоритма ===
'''

Последовательный алгоритм сортировки слиянием основан на принципе «разделяй и властвуй» и включает рекурсивное разбиение массива на две части до подмассивов размера 1. На каждом шаге используется вспомогательная память для копирования левой и правой части массива, после чего выполняется операция слияния, работающая за линейное время. Алгоритм является стабильным и полностью детерминированным, а его асимптотическая сложность составляет . Благодаря независимости обработки левого и правого подмассивов данная реализация хорошо подходит для последующей параллелизации.

'''

=== Возможные способы и особенности параллельной реализации алгоритма ===
'''
Параллельная реализация сортировки слиянием основана на том, что сортировка левой и правой части массива выполняется независимо, что делает алгоритм естественно распараллеливаемым. Основной принцип параллельной версии заключается в создании отдельных задач (threads или процессов), отвечающих за сортировку подмассивов на различных уровнях рекурсивного дерева.
'''

=== Результаты прогонов ===
'''
'''
=== Выводы для классов архитектур ===
'''
Сортировка слиянием хорошо масштабируется на MIMD- и гибридных архитектурах благодаря независимому выполнению подзадач. На SIMD-архитектурах её эффективность ограничена, а на SISD работает предсказуемо, но без ускорения. На распределённых системах ключевым фактором становится оптимизация объёма межпроцессных обменов.
#

== Литература ==
Knuth D.E. The Art of Computer Programming. Volume 3: Sorting and Searching. – 2nd ed. – Addison-Wesley, 1998. – 780 p.

Участник:Kiryan/Алгоритм сортировки слиянием

2025-11-25T15:16:01Z

Kiryan: /* Выводы для классов архитектур */

== Свойства и структура алгоритмов ==
'''
=== Общее описание алгоритма ===
'''
'''Сортировка слиянием''' (англ. ''merge sort'') — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

Алгоритм был изобретён Джоном фон Нейманом в 1945 году
'''
=== Математическое описание алгоритма ===
'''
Пусть задано множество элементов: S = {a1, a2, ..., an} с определенным на нем отношением линейного порядка ≤. Требуется найти такую перестановку π ∈ Sn, что:∀i,j ∈ {1, 2, ..., n}: i < j ⇒ aπ(i) ≤ aπ(j)

Алгоритм реализует стратегию «разделяй и властвуй», состоящую из трех этапов:

# Разделение: Исходный массив рекурсивно делится на две примерно равные части до достижения базового случая (массивы длины 1)
# Упорядочивание: Базовые случаи (массивы длины 1) по определению являются отсортированными
# Слияние: Отсортированные подмассивы объединяются в один отсортированный массив

Операция разделения: SPLIT(A, p, r) = (A[p..q], A[q+1..r]), где q = ⌊(p + r)/2⌋

Операция слияния: MERGE(L, R) = S, где L и R — отсортированные массивы, S — отсортированный массив, содержащий все элементы L и R.
'''
=== Вычислительное ядро алгоритма ===
'''
Вычислительное ядро алгоритма составляет процедура слияния двух отсортированных массивов, которая выполняется на каждом уровне рекурсии и определяет общую производительность алгоритма.
'''
=== Макроструктура алгоритма ===
'''
Алгоритм сортировки слиянием реализует стратегию «разделяй и властвуй» (divide and conquer) и состоит из трех макрофаз:
# Разделения (Divide). Рекурсивная декомпозиция на подмассивы
# Базовые случаи (Conquer). Обработка тривиальных подзадач
# Слияние (Combine). Иерархическое объединение результатов
'''

=== Схема реализации последовательного алгоритма ===
'''
Пусть задан массив
A = [a1, a2, ..., an], ai ∈ R, i = 1, ...,n,
требующий сортировки по возрастанию.

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

=== Последовательная сложность алгоритма ===
'''
На каждом шаге массив размером n делится на две части, каждая из которых рекурсивно сортируется, после чего выполняется операция слияния двух отсортированных подмассивов.

Рекуррентное соотношение для оценки времени работы алгоритма имеет вид:

T(n) = 2T(n/2) + O(n), где O(n) — затраты времени на слияние двух половин массива.

Последовательная временная сложность сортировки слиянием: T(n) = O(nlogn).
'''

=== Информационный граф ===
'''
[[File:Merge_sort.png|800px]]
'''

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

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

'''

=== Входные и выходные данные алгоритма ===
'''
На вход алгоритму подаётся:

* Одномерный массив чисел длиной N, который требуется отсортировать по возрастанию A=[a1,a2,a3,…,aN]
* Количество процессов P, участвующих в вычислении

На выходе алгоритма формируется отсортированный массив длиной N:

A′ = [a'1, a'2, a'3, … , a'N], a'1 ≤ a'2 ≤ ⋯ ≤ a'N
'''

=== Свойства алгоритма ===
'''
Алгоритм сортировки слиянием относится к классу рекурсивных алгоритмов типа «разделяй и властвуй» (divide and conquer).
Параллельная версия основана на независимой обработке подмножеств данных и их последующем слиянии.

Алгоритм реализует параллелизм по данным — каждый процесс сортирует свою часть массива независимо от других.
#

== Программная реализация алгоритма ==
'''
=== Особенности реализации последовательного алгоритма ===
'''

Последовательный алгоритм сортировки слиянием основан на принципе «разделяй и властвуй» и включает рекурсивное разбиение массива на две части до подмассивов размера 1. На каждом шаге используется вспомогательная память для копирования левой и правой части массива, после чего выполняется операция слияния, работающая за линейное время. Алгоритм является стабильным и полностью детерминированным, а его асимптотическая сложность составляет . Благодаря независимости обработки левого и правого подмассивов данная реализация хорошо подходит для последующей параллелизации.

'''

=== Возможные способы и особенности параллельной реализации алгоритма ===
'''
Параллельная реализация сортировки слиянием основана на том, что сортировка левой и правой части массива выполняется независимо, что делает алгоритм естественно распараллеливаемым. Основной принцип параллельной версии заключается в создании отдельных задач (threads или процессов), отвечающих за сортировку подмассивов на различных уровнях рекурсивного дерева.
'''

=== Результаты прогонов ===
'''
'''
=== Выводы для классов архитектур ===
'''
Сортировка слиянием хорошо масштабируется на MIMD- и гибридных архитектурах благодаря независимому выполнению подзадач. На SIMD-архитектурах её эффективность ограничена, а на SISD работает предсказуемо, но без ускорения. На распределённых системах ключевым фактором становится оптимизация объёма межпроцессных обменов.
#

== Литература ==
Knuth D.E. The Art of Computer Programming. Volume 3: Sorting and Searching. – 2nd ed. – Addison-Wesley, 1998. – 780 p.

Участник:Kiryan/Алгоритм сортировки слиянием

2025-11-25T15:15:31Z

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

== Свойства и структура алгоритмов ==
'''
=== Общее описание алгоритма ===
'''
'''Сортировка слиянием''' (англ. ''merge sort'') — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

Алгоритм был изобретён Джоном фон Нейманом в 1945 году
'''
=== Математическое описание алгоритма ===
'''
Пусть задано множество элементов: S = {a1, a2, ..., an} с определенным на нем отношением линейного порядка ≤. Требуется найти такую перестановку π ∈ Sn, что:∀i,j ∈ {1, 2, ..., n}: i < j ⇒ aπ(i) ≤ aπ(j)

Алгоритм реализует стратегию «разделяй и властвуй», состоящую из трех этапов:

# Разделение: Исходный массив рекурсивно делится на две примерно равные части до достижения базового случая (массивы длины 1)
# Упорядочивание: Базовые случаи (массивы длины 1) по определению являются отсортированными
# Слияние: Отсортированные подмассивы объединяются в один отсортированный массив

Операция разделения: SPLIT(A, p, r) = (A[p..q], A[q+1..r]), где q = ⌊(p + r)/2⌋

Операция слияния: MERGE(L, R) = S, где L и R — отсортированные массивы, S — отсортированный массив, содержащий все элементы L и R.
'''
=== Вычислительное ядро алгоритма ===
'''
Вычислительное ядро алгоритма составляет процедура слияния двух отсортированных массивов, которая выполняется на каждом уровне рекурсии и определяет общую производительность алгоритма.
'''
=== Макроструктура алгоритма ===
'''
Алгоритм сортировки слиянием реализует стратегию «разделяй и властвуй» (divide and conquer) и состоит из трех макрофаз:
# Разделения (Divide). Рекурсивная декомпозиция на подмассивы
# Базовые случаи (Conquer). Обработка тривиальных подзадач
# Слияние (Combine). Иерархическое объединение результатов
'''

=== Схема реализации последовательного алгоритма ===
'''
Пусть задан массив
A = [a1, a2, ..., an], ai ∈ R, i = 1, ...,n,
требующий сортировки по возрастанию.

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

=== Последовательная сложность алгоритма ===
'''
На каждом шаге массив размером n делится на две части, каждая из которых рекурсивно сортируется, после чего выполняется операция слияния двух отсортированных подмассивов.

Рекуррентное соотношение для оценки времени работы алгоритма имеет вид:

T(n) = 2T(n/2) + O(n), где O(n) — затраты времени на слияние двух половин массива.

Последовательная временная сложность сортировки слиянием: T(n) = O(nlogn).
'''

=== Информационный граф ===
'''
[[File:Merge_sort.png|800px]]
'''

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

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

'''

=== Входные и выходные данные алгоритма ===
'''
На вход алгоритму подаётся:

* Одномерный массив чисел длиной N, который требуется отсортировать по возрастанию A=[a1,a2,a3,…,aN]
* Количество процессов P, участвующих в вычислении

На выходе алгоритма формируется отсортированный массив длиной N:

A′ = [a'1, a'2, a'3, … , a'N], a'1 ≤ a'2 ≤ ⋯ ≤ a'N
'''

=== Свойства алгоритма ===
'''
Алгоритм сортировки слиянием относится к классу рекурсивных алгоритмов типа «разделяй и властвуй» (divide and conquer).
Параллельная версия основана на независимой обработке подмножеств данных и их последующем слиянии.

Алгоритм реализует параллелизм по данным — каждый процесс сортирует свою часть массива независимо от других.
#

== Программная реализация алгоритма ==
'''
=== Особенности реализации последовательного алгоритма ===
'''

Последовательный алгоритм сортировки слиянием основан на принципе «разделяй и властвуй» и включает рекурсивное разбиение массива на две части до подмассивов размера 1. На каждом шаге используется вспомогательная память для копирования левой и правой части массива, после чего выполняется операция слияния, работающая за линейное время. Алгоритм является стабильным и полностью детерминированным, а его асимптотическая сложность составляет . Благодаря независимости обработки левого и правого подмассивов данная реализация хорошо подходит для последующей параллелизации.

'''

=== Возможные способы и особенности параллельной реализации алгоритма ===
'''
Параллельная реализация сортировки слиянием основана на том, что сортировка левой и правой части массива выполняется независимо, что делает алгоритм естественно распараллеливаемым. Основной принцип параллельной версии заключается в создании отдельных задач (threads или процессов), отвечающих за сортировку подмассивов на различных уровнях рекурсивного дерева.
'''

=== Результаты прогонов ===
'''
'''
=== Выводы для классов архитектур ===
'''
#
== Литература ==
Knuth D.E. The Art of Computer Programming. Volume 3: Sorting and Searching. – 2nd ed. – Addison-Wesley, 1998. – 780 p.

Участник:Kiryan/Алгоритм сортировки слиянием

2025-11-25T15:15:01Z

Kiryan: /* Особенности реализации последовательного алгоритма */

== Свойства и структура алгоритмов ==
'''
=== Общее описание алгоритма ===
'''
'''Сортировка слиянием''' (англ. ''merge sort'') — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

Алгоритм был изобретён Джоном фон Нейманом в 1945 году
'''
=== Математическое описание алгоритма ===
'''
Пусть задано множество элементов: S = {a1, a2, ..., an} с определенным на нем отношением линейного порядка ≤. Требуется найти такую перестановку π ∈ Sn, что:∀i,j ∈ {1, 2, ..., n}: i < j ⇒ aπ(i) ≤ aπ(j)

Алгоритм реализует стратегию «разделяй и властвуй», состоящую из трех этапов:

# Разделение: Исходный массив рекурсивно делится на две примерно равные части до достижения базового случая (массивы длины 1)
# Упорядочивание: Базовые случаи (массивы длины 1) по определению являются отсортированными
# Слияние: Отсортированные подмассивы объединяются в один отсортированный массив

Операция разделения: SPLIT(A, p, r) = (A[p..q], A[q+1..r]), где q = ⌊(p + r)/2⌋

Операция слияния: MERGE(L, R) = S, где L и R — отсортированные массивы, S — отсортированный массив, содержащий все элементы L и R.
'''
=== Вычислительное ядро алгоритма ===
'''
Вычислительное ядро алгоритма составляет процедура слияния двух отсортированных массивов, которая выполняется на каждом уровне рекурсии и определяет общую производительность алгоритма.
'''
=== Макроструктура алгоритма ===
'''
Алгоритм сортировки слиянием реализует стратегию «разделяй и властвуй» (divide and conquer) и состоит из трех макрофаз:
# Разделения (Divide). Рекурсивная декомпозиция на подмассивы
# Базовые случаи (Conquer). Обработка тривиальных подзадач
# Слияние (Combine). Иерархическое объединение результатов
'''

=== Схема реализации последовательного алгоритма ===
'''
Пусть задан массив
A = [a1, a2, ..., an], ai ∈ R, i = 1, ...,n,
требующий сортировки по возрастанию.

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

=== Последовательная сложность алгоритма ===
'''
На каждом шаге массив размером n делится на две части, каждая из которых рекурсивно сортируется, после чего выполняется операция слияния двух отсортированных подмассивов.

Рекуррентное соотношение для оценки времени работы алгоритма имеет вид:

T(n) = 2T(n/2) + O(n), где O(n) — затраты времени на слияние двух половин массива.

Последовательная временная сложность сортировки слиянием: T(n) = O(nlogn).
'''

=== Информационный граф ===
'''
[[File:Merge_sort.png|800px]]
'''

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

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

'''

=== Входные и выходные данные алгоритма ===
'''
На вход алгоритму подаётся:

* Одномерный массив чисел длиной N, который требуется отсортировать по возрастанию A=[a1,a2,a3,…,aN]
* Количество процессов P, участвующих в вычислении

На выходе алгоритма формируется отсортированный массив длиной N:

A′ = [a'1, a'2, a'3, … , a'N], a'1 ≤ a'2 ≤ ⋯ ≤ a'N
'''

=== Свойства алгоритма ===
'''
Алгоритм сортировки слиянием относится к классу рекурсивных алгоритмов типа «разделяй и властвуй» (divide and conquer).
Параллельная версия основана на независимой обработке подмножеств данных и их последующем слиянии.

Алгоритм реализует параллелизм по данным — каждый процесс сортирует свою часть массива независимо от других.
#

== Программная реализация алгоритма ==
'''
=== Особенности реализации последовательного алгоритма ===
'''

Последовательный алгоритм сортировки слиянием основан на принципе «разделяй и властвуй» и включает рекурсивное разбиение массива на две части до подмассивов размера 1. На каждом шаге используется вспомогательная память для копирования левой и правой части массива, после чего выполняется операция слияния, работающая за линейное время. Алгоритм является стабильным и полностью детерминированным, а его асимптотическая сложность составляет . Благодаря независимости обработки левого и правого подмассивов данная реализация хорошо подходит для последующей параллелизации.

'''

=== Возможные способы и особенности параллельной реализации алгоритма ===
'''
'''
=== Результаты прогонов ===
'''
'''
=== Выводы для классов архитектур ===
'''
#
== Литература ==
Knuth D.E. The Art of Computer Programming. Volume 3: Sorting and Searching. – 2nd ed. – Addison-Wesley, 1998. – 780 p.

Участник:Kiryan/Алгоритм сортировки слиянием

2025-11-07T17:51:40Z

Kiryan: /* Свойства алгоритма */

== Свойства и структура алгоритмов ==
'''
=== Общее описание алгоритма ===
'''
'''Сортировка слиянием''' (англ. ''merge sort'') — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

Алгоритм был изобретён Джоном фон Нейманом в 1945 году
'''
=== Математическое описание алгоритма ===
'''
Пусть задано множество элементов: S = {a1, a2, ..., an} с определенным на нем отношением линейного порядка ≤. Требуется найти такую перестановку π ∈ Sn, что:∀i,j ∈ {1, 2, ..., n}: i < j ⇒ aπ(i) ≤ aπ(j)

Алгоритм реализует стратегию «разделяй и властвуй», состоящую из трех этапов:

# Разделение: Исходный массив рекурсивно делится на две примерно равные части до достижения базового случая (массивы длины 1)
# Упорядочивание: Базовые случаи (массивы длины 1) по определению являются отсортированными
# Слияние: Отсортированные подмассивы объединяются в один отсортированный массив

Операция разделения: SPLIT(A, p, r) = (A[p..q], A[q+1..r]), где q = ⌊(p + r)/2⌋

Операция слияния: MERGE(L, R) = S, где L и R — отсортированные массивы, S — отсортированный массив, содержащий все элементы L и R.
'''
=== Вычислительное ядро алгоритма ===
'''
Вычислительное ядро алгоритма составляет процедура слияния двух отсортированных массивов, которая выполняется на каждом уровне рекурсии и определяет общую производительность алгоритма.
'''
=== Макроструктура алгоритма ===
'''
Алгоритм сортировки слиянием реализует стратегию «разделяй и властвуй» (divide and conquer) и состоит из трех макрофаз:
# Разделения (Divide). Рекурсивная декомпозиция на подмассивы
# Базовые случаи (Conquer). Обработка тривиальных подзадач
# Слияние (Combine). Иерархическое объединение результатов
'''

=== Схема реализации последовательного алгоритма ===
'''
Пусть задан массив
A = [a1, a2, ..., an], ai ∈ R, i = 1, ...,n,
требующий сортировки по возрастанию.

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

=== Последовательная сложность алгоритма ===
'''
На каждом шаге массив размером n делится на две части, каждая из которых рекурсивно сортируется, после чего выполняется операция слияния двух отсортированных подмассивов.

Рекуррентное соотношение для оценки времени работы алгоритма имеет вид:

T(n) = 2T(n/2) + O(n), где O(n) — затраты времени на слияние двух половин массива.

Последовательная временная сложность сортировки слиянием: T(n) = O(nlogn).
'''

=== Информационный граф ===
'''
[[File:Merge_sort.png|800px]]
'''

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

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

'''

=== Входные и выходные данные алгоритма ===
'''
На вход алгоритму подаётся:

* Одномерный массив чисел длиной N, который требуется отсортировать по возрастанию A=[a1,a2,a3,…,aN]
* Количество процессов P, участвующих в вычислении

На выходе алгоритма формируется отсортированный массив длиной N:

A′ = [a'1, a'2, a'3, … , a'N], a'1 ≤ a'2 ≤ ⋯ ≤ a'N
'''

=== Свойства алгоритма ===
'''
Алгоритм сортировки слиянием относится к классу рекурсивных алгоритмов типа «разделяй и властвуй» (divide and conquer).
Параллельная версия основана на независимой обработке подмножеств данных и их последующем слиянии.

Алгоритм реализует параллелизм по данным — каждый процесс сортирует свою часть массива независимо от других.
#

== Программная реализация алгоритма ==
'''
=== Особенности реализации последовательного алгоритма ===
'''
'''
=== Возможные способы и особенности параллельной реализации алгоритма ===
'''
'''
=== Результаты прогонов ===
'''
'''
=== Выводы для классов архитектур ===
'''
#
== Литература ==
Knuth D.E. The Art of Computer Programming. Volume 3: Sorting and Searching. – 2nd ed. – Addison-Wesley, 1998. – 780 p.

Участник:Kiryan/Алгоритм сортировки слиянием

2025-11-07T17:44:19Z

Kiryan: /* Входные и выходные данные алгоритма */

== Свойства и структура алгоритмов ==
'''
=== Общее описание алгоритма ===
'''
'''Сортировка слиянием''' (англ. ''merge sort'') — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

Алгоритм был изобретён Джоном фон Нейманом в 1945 году
'''
=== Математическое описание алгоритма ===
'''
Пусть задано множество элементов: S = {a1, a2, ..., an} с определенным на нем отношением линейного порядка ≤. Требуется найти такую перестановку π ∈ Sn, что:∀i,j ∈ {1, 2, ..., n}: i < j ⇒ aπ(i) ≤ aπ(j)

Алгоритм реализует стратегию «разделяй и властвуй», состоящую из трех этапов:

# Разделение: Исходный массив рекурсивно делится на две примерно равные части до достижения базового случая (массивы длины 1)
# Упорядочивание: Базовые случаи (массивы длины 1) по определению являются отсортированными
# Слияние: Отсортированные подмассивы объединяются в один отсортированный массив

Операция разделения: SPLIT(A, p, r) = (A[p..q], A[q+1..r]), где q = ⌊(p + r)/2⌋

Операция слияния: MERGE(L, R) = S, где L и R — отсортированные массивы, S — отсортированный массив, содержащий все элементы L и R.
'''
=== Вычислительное ядро алгоритма ===
'''
Вычислительное ядро алгоритма составляет процедура слияния двух отсортированных массивов, которая выполняется на каждом уровне рекурсии и определяет общую производительность алгоритма.
'''
=== Макроструктура алгоритма ===
'''
Алгоритм сортировки слиянием реализует стратегию «разделяй и властвуй» (divide and conquer) и состоит из трех макрофаз:
# Разделения (Divide). Рекурсивная декомпозиция на подмассивы
# Базовые случаи (Conquer). Обработка тривиальных подзадач
# Слияние (Combine). Иерархическое объединение результатов
'''

=== Схема реализации последовательного алгоритма ===
'''
Пусть задан массив
A = [a1, a2, ..., an], ai ∈ R, i = 1, ...,n,
требующий сортировки по возрастанию.

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

=== Последовательная сложность алгоритма ===
'''
На каждом шаге массив размером n делится на две части, каждая из которых рекурсивно сортируется, после чего выполняется операция слияния двух отсортированных подмассивов.

Рекуррентное соотношение для оценки времени работы алгоритма имеет вид:

T(n) = 2T(n/2) + O(n), где O(n) — затраты времени на слияние двух половин массива.

Последовательная временная сложность сортировки слиянием: T(n) = O(nlogn).
'''

=== Информационный граф ===
'''
[[File:Merge_sort.png|800px]]
'''

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

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

'''

=== Входные и выходные данные алгоритма ===
'''
На вход алгоритму подаётся:

* Одномерный массив чисел длиной N, который требуется отсортировать по возрастанию A=[a1,a2,a3,…,aN]
* Количество процессов P, участвующих в вычислении

На выходе алгоритма формируется отсортированный массив длиной N:

A′ = [a'1, a'2, a'3, … , a'N], a'1 ≤ a'2 ≤ ⋯ ≤ a'N
'''

=== Свойства алгоритма ===
'''
#
== Программная реализация алгоритма ==
'''
=== Особенности реализации последовательного алгоритма ===
'''
'''
=== Возможные способы и особенности параллельной реализации алгоритма ===
'''
'''
=== Результаты прогонов ===
'''
'''
=== Выводы для классов архитектур ===
'''
#
== Литература ==
Knuth D.E. The Art of Computer Programming. Volume 3: Sorting and Searching. – 2nd ed. – Addison-Wesley, 1998. – 780 p.

Участник:Kiryan/Алгоритм сортировки слиянием

2025-11-07T17:37:28Z

Kiryan: /* Ресурс параллелизма алгоритма */

Участник:Kiryan/Алгоритм сортировки слиянием

2025-11-07T17:26:01Z

Kiryan: /* Информационный граф */

Участник:Kiryan/Алгоритм сортировки слиянием

2025-11-07T17:25:37Z

Kiryan: /* Информационный граф */

Участник:Kiryan/Алгоритм сортировки слиянием

2025-11-07T14:13:01Z

Kiryan: /* Последовательная сложность алгоритма */

Участник:Kiryan/Алгоритм сортировки слиянием

2025-11-07T13:58:59Z

Kiryan: /* Схема реализации последовательного алгоритма */

Участник:Kiryan/Алгоритм сортировки слиянием

2025-11-07T13:09:01Z

Kiryan: /* Макроструктура алгоритма */

Участник:Kiryan/Алгоритм сортировки слиянием

2025-11-03T12:09:39Z

Kiryan: Новая страница: «== Свойства и структура алгоритмов == ''' === Общее описание алгоритма === ''' '''Сортировка слия...»

Участник:Kiryan/Алгоритм сортировки вставками

2025-11-03T11:52:06Z

Kiryan: Новая страница: «Основные авторы описания: Деревянкин К.Е. # == Свойства и структура алгоритмов == ''' === Обще...»

Основные авторы описания: Деревянкин К.Е.

#
== Свойства и структура алгоритмов ==
'''
=== Общее описание алгоритма ===
'''
'''Сортировка вставками''' (англ. ''Insertion sort'') — алгоритм сортировки, в котором элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов.
'''
=== Математическое описание алгоритма ===
'''
Пусть задано множество: S = {x₁, x₂, ..., xₙ} ⊆ X, где (X, ≼) — линейно упорядоченное множество. Требуется найти биекцию π: {1,2,...,n} → {1,2,...,n} такую, что: xπ(1) ≼ xπ(2) ≼ ... ≼ xπ(n).
Алгоритм сортировки вставками можно представить как последовательность преобразований массива A:

A(0) = A

A(1) = INSERT(A(0), 1)

A(2) = INSERT(A(1), 2)

...

A(n-1) = INSERT(A(n-2), n-1),

где операция INSERT определяется как: INSERT(B, k) = [b₀, b₁, ..., bj-1, bk, bj, ..., bk-1, bk+1, ..., bm-1], где j = max{i ∈ {0,1,...,k} | ∀l < i: bl ≼ bk} ∪ {-1} + 1

После k-й итерации внешнего цикла (0 ≤ k ≤ n-1) выполняется:

# Элемент маркированного списка
# Подмассив A[0..k] отсортирован: ∀i,j ∈ {0,...,k}: i < j ⇒ A[i] ≼ A[j]
Множество элементов в A[0..k] есть перестановка исходных элементов A0[0..k]
'''
=== Вычислительное ядро алгоритма ===
'''
Вычислительное ядро алгоритма сортировки вставками составляет операция вставки элемента в отсортированную последовательность, которая выполняется на каждой итерации внешнего цикла.
'''
=== Макроструктура алгоритма ===
'''
'''
=== Схема реализации последовательного алгоритма ===
'''
'''
=== Последовательная сложность алгоритма ===
'''
'''
=== Информационный граф ===
'''
'''
=== Ресурс параллелизма алгоритма ===
'''
'''
=== Входные и выходные данные алгоритма ===
'''
'''
=== Свойства алгоритма ===
'''
#
== Программная реализация алгоритма ==
'''
=== Особенности реализации последовательного алгоритма ===
'''
'''
=== Возможные способы и особенности параллельной реализации алгоритма ===
'''
'''
=== Результаты прогонов ===
'''
'''
=== Выводы для классов архитектур ===
'''
#
== Литература ==
Knuth D.E. The Art of Computer Programming. Volume 3: Sorting and Searching. – 2nd ed. – Addison-Wesley, 1998. – 780 p.