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

2025-11-03T11:52:06Z

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

Новая страница

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

#
== Свойства и структура алгоритмов ==
'''
=== Общее описание алгоритма ===
'''
'''Сортировка вставками''' (англ. ''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.

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

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