Участник:Bkmish/Сортировка слиянием (последовательный и параллельный варианты): различия между версиями
Перейти к навигации
Перейти к поиску
Bkmish (обсуждение | вклад) Нет описания правки |
Bkmish (обсуждение | вклад) Нет описания правки |
||
| Строка 3: | Строка 3: | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
Алгоритм сортировки слиянием является методом упорядочивания списков или других структур данных, в которых доступ к элементам может быть получен только последовательно. Этот алгоритм был разработан Джоном фон Нейманом в 1945 году и является хорошим примером использования принципа «разделяй и властвуй», поскольку основан на разбиении главной задачи на более мелкие подзадачи, которые решаются, например, | Алгоритм '''сортировки слиянием''' (англ. merge sort) является методом упорядочивания списков или других структур данных, в которых доступ к элементам может быть получен только последовательно. Этот алгоритм был разработан Джоном фон Нейманом в 1945 году и является хорошим примером использования принципа «разделяй и властвуй», поскольку основан на разбиении главной задачи на более мелкие подзадачи, которые решаются, например, с помощью рекурсивного вызова или непосредственно, если количество элементов рассматриваемой структуры достаточно мало. После этого полученные результаты комбинируются для получения решения основной задачи. | ||
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
| Строка 10: | Строка 10: | ||
== 3 Литература == | == 3 Литература == | ||
* Левитин А. В. Глава 4. Метод декомпозиции: Сортировка слиянием // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 169—172. — 576 с. — ISBN 978-5-8459-0987-9 | |||
* Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4. | |||
Версия от 18:42, 29 октября 2023
Свойства и структура алгоритмов
Общее описание алгоритма
Алгоритм сортировки слиянием (англ. merge sort) является методом упорядочивания списков или других структур данных, в которых доступ к элементам может быть получен только последовательно. Этот алгоритм был разработан Джоном фон Нейманом в 1945 году и является хорошим примером использования принципа «разделяй и властвуй», поскольку основан на разбиении главной задачи на более мелкие подзадачи, которые решаются, например, с помощью рекурсивного вызова или непосредственно, если количество элементов рассматриваемой структуры достаточно мало. После этого полученные результаты комбинируются для получения решения основной задачи.
Математическое описание алгоритма
Вычислительное ядро алгоритма
3 Литература
- Левитин А. В. Глава 4. Метод декомпозиции: Сортировка слиянием // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 169—172. — 576 с. — ISBN 978-5-8459-0987-9
- Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.